Mercurial > hg > Papers > 2016 > atton-ipsjpro

<!DOCTYPE html>
<html>
<head>
   <meta http-equiv="content-type" content="text/html;charset=utf-8">
   <title>Continuation based C を用いたプログラムの検証手法</title>

<meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin14]">
<meta name="author"    content="比嘉健太" >

<!-- style sheet links -->
<link rel="stylesheet" href="s6/themes/projection.css"   media="screen,projection">
<link rel="stylesheet" href="s6/themes/screen.css"       media="screen">
<link rel="stylesheet" href="s6/themes/print.css"        media="print">
<link rel="stylesheet" href="s6/themes/blank.css"        media="screen,projection">

<!-- JS -->
<script src="s6/js/jquery-1.11.3.min.js"></script>
<script src="s6/js/jquery.slideshow.js"></script>
<script src="s6/js/jquery.slideshow.counter.js"></script>
<script src="s6/js/jquery.slideshow.controls.js"></script>
<script src="s6/js/jquery.slideshow.footer.js"></script>
<script src="s6/js/jquery.slideshow.autoplay.js"></script>

<!-- prettify -->
<link rel="stylesheet" href="scripts/prettify.css">
<script src="scripts/prettify.js"></script>

<script>
  $(document).ready( function() {
    Slideshow.init();

    $('code').each(function(_, el) {
      if (!el.classList.contains('noprettyprint')) {
        el.classList.add('prettyprint');
      }
    });
    prettyPrint();
  } );


</script>

<!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
<!--[if IE]>
<script src="s6/js/jquery.microsoft.js"></script>
<![endif]-->


</head>
<body>

<div class="layout">
  <div id="header"></div>
  <div id="footer">
    <div align="right">
      <img src="s6/images/logo.svg" width="200px">
    </div>
  </div>
</div>

<div class="presentation">

  <div class='slide cover'>
    <table width="90%" height="90%" border="0" align="center">
      <tr>
        <td>
          <div align="center">
            <h1><font color="#808db5">Continuation based C を用いたプログラムの検証手法</font></h1>
          </div>
        </td>
      </tr>
      <tr>
        <td>
          <div align="left">
            比嘉健太
            琉球大学 大学院 理工学研究科 情報工学専攻
            <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
          </div>
        </td>
      </tr>
    </table>
  </div>

<div class='slide '>
<!-- === begin markdown block ===

      generated by markdown/1.2.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin14]
                on 2016-08-10 12:46:48 +0900 with Markdown engine kramdown (1.9.0)
                  using options {}
  -->

<!-- _S9SLIDE_ -->
<h1 id="section">ソフトウェアの実装の信頼性の向上</h1>
<ul>
  <li>ソフトウェアの信頼性を向上させたい</li>
  <li>信頼性を向上させる手法には証明、モデル検査、テストなど様々な手法がある</li>
  <li>ソフトウェアが定められた仕様を常に満たすか確認することで信頼性を保証する</li>
  <li>計算を拡張するメタ計算として検証機構を導入し、ソフトウェアの実装コードの検証を行なう</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-1">ソフトウェアの信頼性向上手法</h1>
<ul>
  <li>assert
    <ul>
      <li>実行プログラム上で仕様が満たされているかチェックする</li>
      <li>網羅的にテストできない</li>
      <li>ユニットテストと組み合わせて使う</li>
    </ul>
  </li>
  <li>検証の計算システムで実行する(メタ計算)
    <ul>
      <li>Java Path Finder
        <ul>
          <li>JVM を切り替えてスレッドの実行順番を列挙</li>
        </ul>
      </li>
      <li>Valgrind
        <ul>
          <li>バイナリを動的解析してメモリリークを検出</li>
        </ul>
      </li>
      <li>大規模システムは実行できない</li>
    </ul>
  </li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-2">ソフトウェアの信頼性向上手法</h1>
<ul>
  <li>アルゴリズムの正しさを証明する
    <ul>
      <li>Agda, Coq といった証明支援系でアルゴリズムを記述する</li>
      <li>極めて難しい</li>
      <li>実装に対して適用できない</li>
    </ul>
  </li>
  <li>ソフトウェアの仕様を記述し、その反例が無いかをチェックする
    <ul>
      <li>Spin, NuSMV といったモデルチェッカ</li>
      <li>モデル検査用に特化した言語で実装を記述する必要がある</li>
    </ul>
  </li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="akasha-">Akasha の目的</h1>
<ul>
  <li>実装そのものを検査する
    <ul>
      <li>実装に入り込むバグを見付ける</li>
    </ul>
  </li>
  <li>高速かつ網羅的に検査する</li>
  <li>メタ計算の切り替えで様々な検証を行なう</li>
  <li>高速なメタ計算が行なえる言語(CbC) を用いる</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="continuation-based-c-cbc">Continuation based C (CbC)</h1>
<ul>
  <li>当研究室で開発している言語</li>
  <li>Code Segment, Data Segment という単位でソフトウェアを記述する</li>
  <li>関数呼び出しは末尾のみ、の制約を持ったC言語
    <ul>
      <li>スタックは持たない</li>
      <li>goto で飛んで戻ってこない</li>
      <li>保持すべき状態が明示的になっている</li>
      <li>メタ計算は goto の間に計算を挟むことで実現できる</li>
    </ul>
  </li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="code-segment-and-data-segment">Code Segment and Data Segment</h1>
<ul>
  <li>Code Segment は入出力である Input Data Segment と Output Data Segment を持つ</li>
  <li>単一 Code Segment はシンプル(purely functional)な処理のみを行なう</li>
  <li>Code Segment どうしを接続してソフトウェア全体を構築していく</li>
  <li>依存のない Code Segment どうしは並列に実行することが可能
<img src="./images/code_segment_data_segment.svg" alt="csds" width="50%" /></li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="example-of-code-segment-in-cbc">Example of Code Segment in CbC</h1>
<ul>
  <li>Code Segment は <code>__code</code> を付けた関数</li>
  <li>次の Code Segment への接続は <code>goto</code> で表される</li>
  <li>Data Segment は構造体</li>
</ul>

<pre><code>__code addTen(struct Count c) {
    c.x = c.x+10;
    goto twice(c);
}

__code twice(struct Count c) {
    c.x = c.x*2;
    goto showValue(c);
}
</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="cbc-">CbC のメタ計算</h1>
<ul>
  <li>Code Segment 間の接続はメタ計算レベルで行なわれる</li>
  <li>メタ計算も Code Segment と Data Segment で表現される
    <ul>
      <li>ポインタの扱いや並列実行はメタ計算レベルで行なう</li>
    </ul>
  </li>
</ul>

<p><img src="./images/meta_csds.svg" alt="meta_csds" width="50%" /></p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="cbc--1">CbC のメタ計算の実際</h1>
<ul>
  <li>Code Segment で使われる Data Segment は Meta Data Segment である Context に全て定義されている</li>
</ul>

<pre><code>union Data {
    struct Count {
        int x;
    } count;
    struct Port {
        int port;
    } port;
}

struct Context {
    union Data *data;  // Data Segment
    unsigned int gotoCount; // メタ計算に必要なデータ
};
</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="cbc--2">CbC のメタ計算の実際</h1>
<ul>
  <li>メタ計算レベルでは Data Segment は union Data という形で一様に扱う</li>
  <li>メタ計算と通常の計算は stub と meta によって接続される
    <ul>
      <li>stub では利用する Data Segment の指定などを行なう</li>
    </ul>
  </li>
</ul>

<pre><code>__code addTen_stub(struct Context* context) {
    goto addTen(context, &amp;context-&gt;data[Count]-&gt;count);
}
__code addTen(struct Context* context, struct Count c) {
    c.port = c.x+10;
    goto meta(context, Twice);
}

__code twice_stub(struct Context* context) {
    goto twice(context, &amp;countext-&gt;data[Count]-&gt;count);
}
__code twice(struct Context* countext, struct Count c) {
    c.x = c.x*2;
    goto meta(context, ShowValue);
}
</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="cbc--3">CbC のメタ計算の実際</h1>
<ul>
  <li>goto する時に必ず通る Meta Code Segment <code>meta</code> を作る</li>
  <li>デフォルトの meta
    <ul>
      <li>Code Segment の接続先名から次に実行される Code Segment を決定する</li>
    </ul>
  </li>
  <li>meta を変更することで平行計算や例外処理やソフトウェア検証を行なう</li>
</ul>

<pre><code>__code meta(struct Context* context, enum Code next) {
    goto (context-&gt;code[next])(context);
}
</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="meta-code-segment-">Meta Code Segment を使った例</h1>
<ul>
  <li><code>meta</code> を切り替えることでノーマルレベルの計算を拡張する
    <ul>
      <li><code>goto</code> した回数を数える</li>
    </ul>
  </li>
</ul>

<pre><code>// Meta Data Segment
struct Context {
    union Data *data;       // Data Segment
    unsigned int gotoCount; // メタ計算に必要なデータ
};

// Meta Code Segment
__code meta(struct Context* context, enum Code next) {
    countext.gotoCount++;
    goto (context-&gt;code[next])(context);
}
</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="verification-method-of-programs-using-continuation-based-c">Verification Method of Programs Using Continuation based C</h1>
<ul>
  <li>メタ計算として検証機構を導入する</li>
  <li>仕様はCbCで記述する
    <ul>
      <li>常に真になるべき式として定義</li>
    </ul>
  </li>
  <li>仕様を満たさない Input Data Segment が無いかチェックしていく</li>
  <li>検証の対象として CbC で記述された赤黒木を用いる</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="red-black-tree">Red-Black Tree</h1>
<ul>
  <li>赤黒木とは木構造のデータ構造</li>
  <li>赤黒木の条件:
    <ul>
      <li>各ノードは赤または黒の色を持つ</li>
      <li>ルートと葉の色は黒である</li>
      <li>赤ノードは2つの黒ノードを子として持つ(よって赤ノードが続くことはない)</li>
      <li>ルートから最下位ノードへの経路に含まれる黒ノードの数はどの最下位ノードでも一定である</li>
    </ul>
  </li>
  <li>仕様: 最も長い経路は最も短い経路の高々2倍に収まる</li>
</ul>

<p><img src="./images/rbtree.svg" alt="rbtree" width="35%" /></p>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="verification-library-akasha">Verification Library Akasha</h1>
<ul>
  <li>本研究で作成した検証用メタ計算ライブラリ</li>
  <li>どのような順番で要素が挿入されても常に仕様が満たされることを確認する
    <ul>
      <li>全ての順列組み合わせのテストケースを実行する</li>
    </ul>
  </li>
  <li>仕様を満たさない挿入順番があればそれを表示
    <ul>
      <li>深さ優先探索で有限個の要素の挿入順番を総当たりで列挙</li>
      <li>挿入後の木はきちんとバランスしているかチェックする</li>
    </ul>
  </li>
  <li>CbC のメタ計算 Akasha では要素数13個までチェックできた
    <ul>
      <li>13の階乗の62億通りを8時間ほど</li>
    </ul>
  </li>
  <li>実装にわざとバグを入れた場合にはバランスしない入力例を返した</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="akasha--1">Akasha による赤黒木の検証方法</h1>
<ul>
  <li>挿入される可能性のある全ての要素を持つ循環リストを作成</li>
  <li>木に対して要素を1つ挿入する
    <ul>
      <li>挿入した要素を排除した循環リストを作成</li>
      <li>挿入後に作成された木を保存する</li>
      <li>挿入後の木がバランスされているかをチェックする</li>
      <li>反例用に挿入した要素を記録</li>
    </ul>
  </li>
  <li>全ての要素を挿入したら
    <ul>
      <li>保存していた木と循環リストを再現して深さを高くする</li>
      <li>循環リストの head を1つ進める</li>
      <li>循環リストの head と tail が同じになったら深さを高くする</li>
    </ul>
  </li>
  <li>最初の循環リストの head と tail が同じになったら終了</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="c-bounded-model-checker">C Bounded Model Checker</h1>
<ul>
  <li>Carnegie Mellon University で開発されている記号実行モデルチェッカ
    <ul>
      <li>C, C++, Java に対応</li>
    </ul>
  </li>
  <li>CbC は <code>__code</code> を <code>void</code> に、<code>goto</code> を <code>return</code> に変えると C Syntaxになる
    <ul>
      <li>赤黒木のコードを機械的に置換で C に変換して検証</li>
    </ul>
  </li>
  <li>挿入順番は非決定的な入力 <code>nondet_int</code> を使う</li>
  <li>関数呼び出しやループは展開される
    <ul>
      <li>展開可能な最大数まで展開した時、バグを含んだ赤黒木の仕様を検証できず</li>
    </ul>
  </li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="conclusion">Conclusion</h1>
<ul>
  <li>動作するプログラムの記述を変更せず検証を行なえた
    <ul>
      <li>テストケースの自動生成+仕様の反例表示ができた</li>
    </ul>
  </li>
  <li>CBMC では検証できない範囲の検証を行なうことができた
    <ul>
      <li>総当たりでチェックしているため扱えるサイズは小さい
        <ul>
          <li>CBMC に比べ高速</li>
        </ul>
      </li>
      <li>記号実行しているわけではない
        <ul>
          <li>有限の個数しか扱えない</li>
        </ul>
      </li>
    </ul>
  </li>
  <li>ポインタアクセスに由来するバグなどは見付けられない</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="future-works">Future Works</h1>
<ul>
  <li>状態の抽象化による探索の効率化</li>
  <li>挿入だけでなく削除を含む赤黒木の仕様検証</li>
  <li>ポインタへの不正アクセス検出などの機能</li>
  <li>検証用APIを CbC コンパイラに導入</li>
  <li>CBMC 側での赤黒木検証を検討する</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="akasha-execution-environment">Akasha Execution Environment</h1>
<ul>
  <li>Intel(R) Xeon(R) CPU E5-2699 v3 @ 2.30GHz 18 core</li>
  <li>メモリ: 768G</li>
  <li>Compile Option: -O0</li>
  <li>要素数10個: 11sec (362万通り)</li>
  <li>要素数11個: 136sec (3991万通り)</li>
  <li>要素数12個: 1554sec (4億7900万通り)</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="cbmc-informations">CBMC Informations</h1>
<ul>
  <li>CBMC 5.4</li>
  <li>実行オプション
    <ul>
      <li>cbmc –depth 400 –property verifySpecification.assertion.1</li>
    </ul>
  </li>
  <li>赤黒木のCbC実装
    <ul>
      <li>赤黒木部分のみ: 330行</li>
      <li>スタックやメモリのアロケータなどを含む: 640行</li>
    </ul>
  </li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="section-3">他の言語でのメタ計算</h1>
<ul>
  <li>計算を実現するような計算</li>
  <li>プログラムを生成するようなプログラム
    <ul>
      <li>TemplateHaskell in Haskell, Template in C++, Generics</li>
      <li>コンパイル時メタプログラミング</li>
    </ul>
  </li>
  <li>言語が特別な API を提供する
    <ul>
      <li>method_missing, define_method in Ruby</li>
    </ul>
  </li>
  <li>プログラムがその言語処理系の挙動を変える
    <ul>
      <li>reflection in Java</li>
    </ul>
  </li>
  <li>CbC では関数呼び出しが存在していないのでメタ計算を挟むことが容易</li>
</ul>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="red-black-tree-">Red-Black Tree のコード例</h1>

<pre><code>__code insertCase2(struct Context* context, struct Node* current) {
    struct Node* parent;
    stack_pop(context-&gt;node_stack, &amp;parent);

    if (parent-&gt;color == Black) {
        stack_pop(context-&gt;code_stack, &amp;context-&gt;next);
        goto meta(context, context-&gt;next);
    }

    stack_push(context-&gt;node_stack, &amp;parent);
    goto meta(context, InsertCase3);
}

__code insert2_stub(struct Context* context) {
    goto insertCase2(context, context-&gt;data[Tree]-&gt;tree.current);
}
</code></pre>


</div>
<div class='slide '>
<!-- _S9SLIDE_ -->
<h1 id="akasha--2">Akasha の検証コード例</h1>

<pre><code>__code verifySpecificationFinish(struct Context* context) {
    if (context-&gt;data[AkashaInfo]-&gt;akashaInfo.maxHeight &gt;
        2*context-&gt;data[AkashaInfo]-&gt;akashaInfo.minHeight) {
        context-&gt;next = Exit;
        goto meta(context, ShowTrace);
    }
    goto meta(context, DuplicateIterator);
}
</code></pre>

<!-- vim: set filetype=markdown.slide: -->
<!-- === end markdown block === -->
</div>


</div><!-- presentation -->
</body>
</html>
author	Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date	Sun, 11 Dec 2016 17:10:39 +0900
parents	f5cad08f76b5
children