4

Cプログラムの効率的なコンテキスト依存ポインター分析に関する論文のStrongUpdateセクションを読んでいますが、それが何を意味するのか正確に理解できません。誰かが例を提供できますか、特にリンクのこの行について：

これにより、強力な更新を実行する能力が大幅に向上します。ヒープブロックは特定のコンテキストで割り当てられたすべてのストレージを表すため、ローカルに割り当てられたヒープブロックは決して一意ではないと想定します。

4

1 に答える 1

5

強い更新、弱い更新

プログラムのすべての可能な動作を一度に推測しようとする静的解析のコンテキストでは、強力な更新は、更新されるアドレスが正確にわかっている更新 (割り当て) 操作です。対照的に、書き込まれたアドレスが正確にわからない割り当ては、弱い更新と呼ばれます。

弱い更新を処理する場合、新しい値が複数の場所に書き込まれる可能性があるだけでなく、どの場所かがわからないだけでなく、さらに、各場所が古い値を保持している可能性を考慮する必要があります (更新は別の場所で発生する可能性があるため)。

例

Frama-C の value analysisを検討してください。これは、ほとんどの Linux ディストリビューションでパッケージとして利用できる C プログラムの効率的な状況依存ポインター分析です。次のプログラムを分析しているとしましょう。

int a, b, c, d, *p, t[5];

int main(int argc, char **argv){
  a = 1; // strong
  p = &b;
  *p = 2; // strong
  if (c & 1) 
    p = &c;
  else
    p = &d;
  *p = 3; // weak

  t[2] = 4; // strong
  t[c & 2] = 5; // weak
}

この例を Frama-C の価値分析で分析すると、次のようになります。

$ frama-c -val t.c
[value] Values at end of function main:
  a ∈ {1}
  b ∈ {2}
  c ∈ {0; 3}
  d ∈ {0; 3}
  p ∈ {{ &c ; &d }}
  t[0] ∈ {0; 5}
   [1] ∈ {0}
   [2] ∈ {4; 5}
   [3..4] ∈ {0}
  __retres ∈ {0}

ロケーションc、d、t[0]およびt[2]は、弱い更新の対象となっています。それぞれに、新しい値 (そこに書き込まれた可能性がある) または古い値 (その時点で存在し、残っている可能性がある) のいずれかを含めることができます。

反対により、強力な更新の対象aとなっています。b割り当てがこれらの変数のそれぞれに正確に書き込んでいることがわかっていたので、それらが古い値を保持している可能性を考慮する必要はありません。

記事の文脈では

あなたが引用する正確な段落について：

重要なのは、一意のポインターの初期値を表す拡張パラメーターが、そのポインターが呼び出しコンテキストで多くの可能な値を持っている場合でも、一意のブロックになる可能性があることを認識することです。ポインタには一度にこれらの可能性の 1 つしか含めることができないため、拡張パラメータはプロシージャのスコープ内で一意のブロックになります。複数の場所が拡張パラメーターを指し、そのパラメーターの実際の値が単一の一意の場所ではない場合にのみ、パラメーターを一意ではないものとしてマークする必要があります。これにより、強力な更新を実行する能力が大幅に向上します。

研究者は、より正確であるため、できるだけ頻繁に強力な更新を使用することを目指しています。このパラグラフでは、ポインターは複数の可能な場所を指している可能性がありますが、「その場所が指すp場所」に名前を付けると、その場所を強力に更新できると述べています。pこれが彼らの言っていることだと思います。

これにより、私のサンプル プログラムでは、プログラムの最後で から読み取り、正確に が含まれていること*pがわかります。Frama-C の価値分析の古いバージョンでは、説明されているのと同様の手法でこの情報を推測していましたが (私の理解が正しければ)、コストが高すぎたため削除されました。3pc03d03

于 2012-11-03T08:51:26.393 に答える