Bantako's notes garden

Learning to Fuzz from Symbolic Executionwith Application to Smart Contracts

61 min read

2022-05-22

  • Author:
    • He J
    • Balunović M
    • Ambroladze N
    •  et al.
  • Title:Learning to fuzz from symbolic execution with application to smart contracts
  • Journal:Proceedings of the ACM Conference on Computer and Communications Security
  • Issue:
  • Page:531-548
  • Year:2019
  • URL:https://dl.acm.org/doi/abs/10.1145/3319535.3363230 #paper

abstract

ファジングとシンボリック実行は，ソフトウェアの脆弱性を発見するための補完的な技術である．ファジングは高速でスケーラブルであるが，正しい入力をランダムに選択できない場合は効果がないことがある．また，記号実行は，複雑なパス条件を持つ深いプログラムパスに対して拡張性がない場合が多く，徹底的であるが低速である． 本研究では、模倣学習の枠組みで学習課題を表現することで、効果的で高速なファザーを記号実行から学習することを提案する。学習中、記号実行の専門家は数千のプログラムのカバレッジを向上させるために、多数の品質入力を生成する。次に、生成されたデータセットに対して、ニューラルネットワークの適切なアーキテクチャで表現されたファジングポリシーが学習される。学習された方針は、新しいプログラムをファジングするために用いることができる。この領域では、契約はしばしば類似の機能を実装し（学習を容易にする）、セキュリティが最も重要である。 我々は、エンドツーエンドのシステムであるILF（for Imitation Learning based Fuzzer）と、18K以上のコントラクトに対する広範な評価を提示する。ILFは、(i)1秒間に148トランザクションを生成する高速性、(ii)既存のファザーよりも優れた性能（例えば、33%以上のカバレッジを達成）、(iii) Ethereum用の既存のファジングおよびシンボリック実行ツールよりも多くの脆弱性を検出する、などの効果があることが示された。

  • term
    • fuzzing
      • ファジングとは、ソフトウェアテストの手法の一つで、ファズ（fuzz）と呼ばれる通常想定されていない「不正データ」「予期せぬデータ」「ランダムなデータ」を対象の製品・システムに与え意図的に例外を発生させ、潜在的なバグ・脆弱性を検出する手法です。
      • https://www.veriserve.co.jp/service/detail/fuzzing.html
    • Imitation learning
      • 教師あり強化学習：模倣学習
      • https://recruit.gmo.jp/engineer/jisedai/blog/imitation-learning/
      • 主な手法
        • （１）Behavoir Cloning：専門家データを完全に信用し、専門家の動作を丸ごとコピーするように、行動Policyを構築する。
        • （２）Dataset Aggregation：専門家の行動データと学習した行動ポリシーによる行動データを融合しながら、新しいデータセットの上に、行動ポリシーを更新する。
        • （３）Inverse Reinforcement Learning：専門家のPolicyを学習することではなく、専門家データから報酬関数Reward(State, Action)を推定する。（状態、動作）をインプットすれば、報酬が分かるとすると、行動ポリシーも自然に決められる。
    • symbolic execution
    • Smart contraction
    • ILF
    • Ethereum

Introduction

実世界のプログラムを効果的にファジングするための重要な課題は，実世界のプログラムに対してファジングを行い，その結果をターゲットプログラムに適用することでセキュリティの脆弱性を発見することです．実世界のプログラムを効果的にファジングするための重要な課題は，プログラムのコードを徹底的に実行する入力を生成することである [21, 30, 38, 68]．ランダムファザーは，プログラムの深い経路を実行できない効果的でない入力にしばしば引っかかり，その結果，バグを見落とす可能性があります[22,45,48,53]．記号実行は，市販の制約ソルバを利用してパス制約を解くことができるため，効果的な入力を生成するために使用されてきました．この制約によって，プログラムの実行が特定のパスに沿って誘導され，カバレッジが向上したり，新しい脆弱性が露出したりします［13，14，52，67］．記号的な専門家からファジングを学ぶ。我々は，記号的な実行によって生成される高品質な入力は，効果的なファザーを学習するために使用できる貴重な知識ベースを形成することを核心的な洞察としています．我々は、模倣学習[49]の枠組みを用いて、記号実行の専門家によって生成された入力からファザーを学習することを提案する。このアプローチは、自律走行[47]、ロボット工学[4]、ゲームプレイ（例えば、学習したモデルが囲碁で超人的なパフォーマンスを達成した[57]）など様々な分野で成功裏に適用されてきた。このフレームワークでは，弟子（我々の設定ではファザー）が，強力だが実行コストがかかるエキスパート（記号実行エンジン）の振る舞いを模倣することを学習する．学習されたファザーは、ファジングと記号実行の両方の長所を兼ね備えています。 効果的な入力を素早く生成することができます。私たちは 学習したファザーを使って未知のプログラムをテストすることができる。このハイレベルな考え方を図1に示す。学習段階では、カバレッジガイド付き記号実行エキスパートを数万個のプログラムに対して実行し、学習用入力シーケンスのデータセットを生成します。シンボリック実行エキスパートの動作を学習するために、プログラム入力を生成するための確率的ファジングポリシーを取り込んだニューラルネットワークを適切に学習させる。ニューラルネットワークは、得られたデータセットに対して高い精度が得られるように学習される（つまり、記号実行エキスパートがうまく模倣される）。学習後、学習された方針を用いて、未知のプログラムをファジングするための入力列を生成する（図1下段）。ファザーは各ステップで、ファジングポリシーから入力をサンプリングし、プログラムに対してそれを実行し、状態を更新してファジング処理を継続する。本論文は、模倣学習の枠組みをプログラムテストに適用した最初の研究である。

応用領域 スマートコントラクトのファジング 我々はファジングアプローチを（ブロックチェーン）スマートコントラクトのドメインに適用します。これは、Ethereum [65]などの分散台帳の上で実行されるプログラムであります。スマートコントラクトはしばしばトークンや分散型クラウドセール[43]などの類似の機能を実装しているので、我々はこのドメインが我々の学習アプローチに特に適していると考えている。実際、最近の研究は、実世界の契約間で実質的なコードの類似性があることを実証している[34]。これにより、新しい未見のスマートコントラクトをファジングする方法をシンボリック実行の専門家から学ぶことが可能になります。さらに、スマートコントラクトは、効果的にファジングすることが困難であることが証明されています。概念的には、それらはステートフルなプログラムであり、台帳の永続的な状態を変更するトランザクションのシーケンスを処理します。スマートコントラクトの高いカバレッジを達成するための主な障害は、一部の関数がより深い状態（例えば、クラウドセールが終了した後）でのみ実行できることです。実際、Echidna [17]やContract Fuzzer [32]などのコントラクト用の既存のファザーは、より深いパスをカバーできず脆弱性を露呈する可能性のあるトランザクションのシーケンスをランダムに生成します。さらに、既存の記号実行エンジン[37, 42]は、限られた数のトランザクション（例えば3）を記号的に推論することしかできず、より深い状態に到達することができないのです。したがって、スマートコントラクトの高カバレッジのファジングは、特にコントラクトの脆弱性がすでに大きな金銭的損失をもたらしているため、重要な未解決問題のままです[44, 60]。ILFのシステムと評価 我々のアプローチに基づき、我々は、実世界の契約（イーサリアム上に展開された）上で高いカバレッジを達成するトランザクションのシーケンスを生成するイーサリアムのための新しいファザーであるILF1（Imitation Learning based Fuzzerの意）を提示します。

18,000のスマートコントラクトを対象としたILFの広範な評価を発表する。我々の結果は、学習されたファザーが実用的に効果的であることを示しています。まず、ILFは高速で、1秒間に平均148のトランザクションを生成・実行します。第二に、ILFは既存のファジングアプローチよりも優れており、大規模なコントラクト（3K以上の命令）においてEchidnaよりも33％高いカバレッジを達成しました。第三に、Ethereumのための既存のファジングや記号実行ツールよりも多くの脆弱性を特定します。例えば、記号実行に基づくツールであるMaian [42]よりもおよそ2倍多くのリーク脆弱性を検出します。主な貢献 要約すると、我々の主な貢献は以下の通りです。

  • 記号的実行の専門家を模倣する学習に基づく新しいファジングアプローチ．
  • スマートコントラクトの入力シーケンスを生成するためのファジングポリシーをモデル化する新しいニューラルネットワークアーキテクチャ（セクション4）。
  • ILFと呼ばれるエンドツーエンドの実装は、スマートコントラクトのファジングに合わせた意味的特徴表現、スマートコントラクトのための実用的な記号的実行エキスパート、および重要な脆弱性検出器のセットをサポートします(セクション5)。
  • 18K以上の実世界のスマートコントラクトに対する広範な評価により、ILFが高速で、高いカバレッジ（平均92％）を達成し、スマートコントラクト用の既存のセキュリティツールよりも大幅に多くの脆弱性を検出することを実証しています（セクション6）。

2. Overview

この契約は、高いカバレッジを達成するトランザクションを生成するための重要な課題を浮き彫りにするものです。

2.1 動機となる例

動機となる例として、Ethereum [65]上のスマートコントラクトの最も一般的なパラダイムの1つであるクラウドセールを提示します。クラウド・セールの目標は、60 日以内に 10 万エーテルを集めることである。この目標が60日以内に達成された場合、クラウドセールは成功し、その場合、クラウドセールのオーナーは資金を引き出すことができる。図 2 は，広く使われている OpenZeppelin ライブラリ [43] を利用した Solidity コード [3] を示している．クラウドセールのコンストラクタは，クラウドセールの終了日をデプロイ時から 60 日に初期化し（now が返す），クラウドセールのクリエータ（msg.sender が返す）をそのオーナーとして割り当てる．この関数は、クラウドセールがアクティブ（phase = 0）かつゴールに到達していない（raised<goal）場合のみ実行される。この関数は、調達したエーテルの額が目標額と同じかそれを上回る場合にのみフェーズを1（クラウドセールの成功を示す）に変更し、現在の時刻（現在）がクラウドセールの終了時刻を超え、調達した資金の額が目標額に満たない場合にのみ2（クラウドセールの失敗を示す）に変更することを保証するものである。クラウドセールがフェーズ1にある場合、投資したエーテルは関数withdrawで所有者に譲渡することができる。脆弱性：本クラウドセール契約には，[42]で定義されたLeakingと呼ばれる脆弱性が存在する．この脆弱性は，コントラクトが一度もエーテルを送ったことのない，信頼されていないユーザにエーテルを送った場合に発生する．ここで、信頼できるユーザーのセットは、コントラクトの作成者と、信頼できるユーザーによって送信されたトランザクションの引数としてアドレスが表示されているすべてのユーザーで構成され、残りのすべてのユーザーは信頼できないとみなされる。この定義により、契約書の所有権や管理権限が信頼されていないユーザに譲渡されないことが保証される。このクラウドセールの例における脆弱性は、次のような一連のトランザクションによって引き起こされる：t1: t1: ユーザがmsg.value≥goalでinvest()を呼び出す;t2: このシーケンスでは、(i)攻撃者がコントラクトにエーテルを送らない（攻撃者のトランザクションst3およびt4はmsg.値がデフォルトで0に設定されている）、(ii)攻撃者がコントラクトにエーテルを送らない（攻撃者のトランザクションst3およびt4はデフォルトで0に設定されている）という理由から脆弱性が露呈しています。このシーケンスでは、(i)攻撃者がコントラクトにエーテルを送らず（攻撃者のトランザクションst3とt4はデフォルトで0に設定）、(ii)攻撃者のアドレスAは信頼されうるユーザーによって送られるトランザクションの引数に使われないため信頼されないが（int1およびt2）、 (iii) 攻撃者がエテルを受信する（int4）ことから、脆弱性が露呈する。本脆弱性は、関数 setOwner の事前条件として、owner への呼び出しを制限する必要があること（29 行目）を示しています。

2.2 スマートコントラクトのファジングの課題

スマートコントラクトはステートフルなプログラムである．各コントラクトは永続的なストレージを持ち、クラウドセールの例で調達された資金量のような、トランザクションに関連する状態を保持する（図2）。コントラクトが処理する各トランザクションは、コントラクトの状態を変更する可能性がある。例えば、ユーザーがクラウドセール契約の関数investを正の量のエーテルで呼び出した場合（すなわち、msg.value>0）、調達資金の量が増加する。より具体的には，各取引は，(i)実行するコントラクト関数とその関数が必要とする引数，(ii)取引を開始したユーザのアドレス，(iii)コントラクトに転送されたイーサーの量によって識別される．例えば、我々のクラウドセールは、ユーザーが十分な量のエーテルをコントラクトに投資した後（functioninvestの呼び出しによって）、phase=1が維持される状態になることがあります。この課題は、コントラクトをテストする際に達成できるコードカバレッジに直接影響します。コントラクトの関数には、関数が実行されるために満たさなければならない状態に関する事前条件が定義されていることがよくあります。例えば、クラウドセールの例では、phase = 1holds のときだけ関数withdrawが実行されます。次に，既存のファザーと記号実行ツールは高いコードカバレッジを達成するのに苦労し，その結果，状態空間のより深いところに潜む脆弱性を誘発することを説明する．その結果，Echidnaは57%のコードカバレッジを達成した．達成したカバレッジをよく観察すると，Echidnaは関数setPhase，withdraw，およびrefundをカバーできていないことがわかる．また、関数etPhaseは引数newPhase∈{1,2}を生成する必要があります。既存の記号実行ツールのスケーラビリティの限界スマートコントラクトは小さいことが多いですが、記号実行を用いて徹底的に分析することは困難です。これは、より深い状態でのみ明らかになるバグを発見するために、トランザクションのシーケンスを記号的に推論する必要があり、ブロック状態の爆発と複雑な制約をもたらすからです。具体的には、シンボリックなブロック状態の数は、解析したシンボリックトランザクションの深さkに対して指数関数的に増加する。このスケーラビリティの問題に対処するため、既存の記号実行ツール[37,42]は深さを制限し（例えば、通常2-3トランザクション）、実行可能なパスのサブセットを（ヒューリスティクスを用いて）解析しています。実際、Leaking 脆弱性をサポートする記号実行ツール Maian[42] は、我々のクラウドセールの例で、解析深度を 4 に上げても（デフォルトの深度は 3）脆弱性を発見できない。

2.3 ILFFuzzer

上記の制限に対処するため，我々は，トランザクション列の生成に確率的ファジングポリシーを用いる新しいファザーであるILFを開発した．このファザーは、スケーラブルな記号実行エキスパートを実世界の契約に対して実行することによって生成された何万もの高品質なトランザクションシーケンスから学習される。この専門家は具体的なブロック状態を操作し、具体的な取引シーケンスを生成するために記号的な実行を採用する。このエキスパートが生成するトランザクション列は、十分な長さがあり（平均で30）、適度に深い状態に到達することが可能である。我々のエキスパートに関する詳細は5.2節で述べる。以下，学習されたファジングポリシーがどのように取引を生成するかを説明する．ファジングポリシーを図3に示す．入力として，テスト対象の契約とこれまでに実行されたトランザクションの履歴から得られた意味情報を受け取り，トランザクションのシーケンスを拡張するために使用できる候補トランザクションのセットに対する確率分布を出力する．tia を選択する前に生成されたトランザクションは、図 3 の左上の表に示されている。例えば、トランザクションti-1は、アドレス0x10と0etherを持つユーザーによって送信されたfunctionsetPhase(1)へのコールである。このシーケンスに基づき、ILFはコントラクトの各関数（invest、setPhaseなど）に対する特徴ベクトルを導出する。これらの特徴 (セクション 5.1 で定義) は、カバレッジの向上を目的とした新しいトランザクションの生成に関連するドメイン固有の知識を捕捉する。この特徴行列と隠れ状態hi-1を用いて，ファジングポリシーは図3の右上に示すようないくつかの分布を出力する．ILFは（i）関数と引数のリスト，（ii）トランザクション送信者のアドレス，（iii）トランザクションに添付されるエーテルの量をサンプルとしている．これらの構成要素はまとめて、次に実行されるトランザクションを特定する。この例では、ILFはユーザー0x20によって送信されたinvest()を選択し、大量のエーテル(99..99で示される)を送信する。最後に、tiを選択した後、ILFは隠れ状態hiを更新し、次のファジングステップでトランザクションを選択するためにそれを後で使用する。この問題に対処するために、我々は慎重に作られたニューラルネットワークアーキテクチャを提示し、可変数の引数と大きな領域型（例えば、整数）を扱うことを含む関連する課題に対処する。このアーキテクチャについてはセクション4.2.Coverage and Vulnerability Detectionで詳述する．ILFの主な利点は，ファジングポリシーの計算速度が速いこと（ILFは148trans-action/sでファジングする），しかし高いcoverage（我々のデータセットでは平均92%）を効果的に達成できることである．ILFは脆弱性を発見するために、Leaking vul-nerabilityの検出を含む6つの検出器をサポートしている。セクション6では、ILFの広範な評価を行い、コードカバレッジと脆弱性検出の両方において、既存のファジングツールや記号的実行ツールに対するILFの優位性を実証する。

3 background

本節では，イーサリアムスマートコントラクト，模倣学習，関連するニューラルネットモデ ルに関する背景を説明する

3.1 Ethereum smart contract

また、Ethereum は契約アカウントもサポートしており、このアカウントは自律的なエージェントであり、実装をコード化し、状態を台帳に保存する。契約は、取引（ユーザーからの送信）またはメッセージ（他の契約からの呼び出し）により実行される。EVM 命令セットは、コントラクトの状態の読み取りと書き込み（sstore と load）、現在のブロックのタイムスタンプの読み取り、トランザクション送信者のアドレス（呼び出し元）の読み取りなどのためのトップコードなどの標準的な命令をサポートしています。 ここで、f(x)はコントラクトのパブリックまたは外部関数fとその引数x、senderはトランザクションの送信者のアドレス、amountはコントラクトに転送されるエーテル量であることを識別する。関数は支払い可能であり、エーテルを受け取ることができる。支払い不可能な関数は、金額が0より大きい場合、元に戻されます。可能なすべてのトランザクションの集合をTと書く。 トランザクションは呼び出されたコントラクトと呼び出された他のコントラクトのストレー ジを変更することができる。形式的には、トランザクションtatブロック状態の実行の効果はbt→b′で捕捉される。初期ブロック状態binit（Band）が一連の取引st=（t1,…,tn）∈T＊であるとすると、ttによって引き起こされるブロック状態のシーケンスbinitt1→ ---tn→bnはブロック状態トレースと呼ばれる。 マルコフ決定過程マルコフ決定過程（MDP）は、逐次的な意思決定問題をモデル化するための数学的なフレームワークである。MDPは、ある環境下でエージェントが意思決定を行い、その結果を獲得することを含む。ここで、Sは状態の集合、Aは行動の集合、E:S×A →Sは状態遷移関数、R:S×A →Rは報酬関数である。MDPを解く目的は、ステップ間の期待累積報酬を最大化する確率的政策πopt:S×A → [0,1]を学習することである。エージェントは新しい状態を観測するたびに、学習された政策から行動をサンプリングすることができる。この最適化問題を解くために、我々は模倣学習[49]の枠組みを採用する。このアプローチでは、与えられたタスクで高い報酬を得ることができる既存の経験的な方針π＊を利用する。しかし、π＊は多くの場合、時間的複雑性が高く、手作業が必要です（我々の場合、π＊は記号実行エンジンです）。模倣学習では、π＊を用いた実証実験を行うことで、より計算量が少なく、理想的にはπ＊と同じ報酬を得られる反抗的な政策ˆπを学習することができます。 ここで、各サンプル[(si,ai)]d∈(S×A)＊は、状態iに遭遇したときπ＊が行動aiをとるという意味の状態-行動ペアの列である。そして、ある状態が与えられたときに、取り得る行動の確率ベクトルを出力し、π＊が取る行動に対して最も高い確率を割り当てることを目的とした分類器ConDを学習します。学習された分類器Cは，我々の弟子入り方針ˆπを表している．もしChがデータセットDに対して高い予測精度を持つならば、ˆπはπ*を忠実に模倣することになります。3.3 ニューラルネットワークモデル4.2節で説明したファジングポリシーを表現するためのニューラルネットワークモデルを概観する。非直線性を持たせるために，ニューロンは活性化関数(例えばReLUやSigmoid)を通過させる．Gated Recurrent Unit.Gated Recurrent Unit (GRU) [16]は、Recurrent Neural Networks (RNN) の一種で、可変長のシーケンシャル入力を扱うモデルである。GRUは、内部状態と記憶を保持することで、シーケンスの履歴を追跡することが可能である。GRUはステップiごとに入力xi（Rm）を受け取り、最後の状態embeddinghi-1（Rn）に基づき、新しい状態embeddinghi（Rn）を計算する。この操作は、hi=GRU(xi,hi-1)と特徴づけることができる。また、GRUは内部で更新gatezi（Rn）とリセットgateri（Rn）を計算し、過去の情報を保持するか消去するか決定します。GRUの詳細については、[16]を参照されたい。

4 Fuzzing policy

このセクションでは，模倣学習の概念をスマートコントラクトのカバレッジベースのファジングの問題に適用する．

4.1 Formulating Fuzzing as MDP

Table 1 は，MDP の主要な構成要素がスマートコントラクトのカバレッジベースのファジングの概念とどのように結びつくかを示している．テストされた契約cとその初期ブロック状態binitは、契約をファジングするときに固定される。したがって、乱雑さを避けるために、正式な定義からそれらを省略する。ファジングポリシーが取引の全履歴に基づいて判断できるように、状態を取引のシーケンスとして表現する。ステップiで、一連の取引sti=(t1,…,ti-1)と、テスト中の契約を実行したときに生じたブロック状態の痕跡binitt1→ ---ti-1→bi-1 に基づいて、エージェントはポリシーπに基づいて実行する新しい取引titoを選択する。目標は、ファジングの終了時にできるだけ多くのカバレッジを得ることである（トランザクションの限界またはタイムリミットに達する）。ここでは、ファジングポリシーを正式に定義し、このセクションの後半で異なるポリシーを具体化する。ファジングポリシー：ファジングポリシーは関数π：T＊×T→[0,1]で表現される。すなわち，現在の状態とキャンディデートトランザクションが与えられたとき，そのトランザクションを選択する確率を出力する．スマートコントラクトの取引は複雑な構造を持つため、ファジングポリシーを以下の4つの要素に分解する：（1）πfunc：T＊×F→ [0,1] 、F={f1,…}から関数を選択するために使用する。 (2)πargs:T∗×F×X∗→[0,1]: 選択された関数fの引数xを選択するために用いる。 (4）πamount：T＊×F×AMT→[0,1]選択された関数fの支払い金額を選択する。 なぜなら、πargsで選択される引数の数はfのアリティに依存し、πamountで選択されるエーテルの量は0iffが非支払可能な関数であるからです。 トランザクションの構築 新しいトランザクションを生成するために使用されるファジング方針πは、トランザクションstの履歴に基づくサンプリングプロセスとして定義される。 (f(x),sender,amount)∼π(t)：f∼πfunc(t) はサンプルされた関数、 x∼πargs(t,f) はサンプルされたfの引数のリスト、 sender∼πsender(t) はサンプルされたedender、 amount∼πamount(t,f) はサンプルされたイーサー量、である。 例：一様乱数政策。 一様にランダムに取引を選択するポリシーπunifを例として示す。 πuniffunc(t)=Unif(F),πunifargs(t,f)=Unif(Sig(f)), πunifsender(t)=Unif(SND), πunifamount(t,f)=(Unif([0,MA])fis payable{0→1}otherwishereUnif(X)returns a uniform distribution over domainX, Sig(f)returns the set of arguments that comply with f’s signature, and MA is the maximum amount of ether for a transaction.ここで、Unif(X)はdomainX上の一様分布を、Sig(f)はfの署名に従う引数のセットを、MAは取引のためのエーテルの最大量を返す。我々はこのポリシーをセクション6でベースラインの1つとして使用する。

4.2 Neural Network-based policy

ニューラルネットワークベースのファジングポリシーπnnを図4に示すようなニューラルネットワークモデルのアーキテクチャで表現する．ファジング状態ファジング中のトランザクションの履歴から情報を記憶するために，GRUを用いてファジング状態を符号化する．図4のボックス[0]に示すように、隠されたファジング状態hi∈Rnisは次のように計算される：hi=GRUfuzz(αfi-1(F,ti),hi-1) ここでhi-1∈Rnisは最後のファジング状態のエンコーディング、 αfi-1(F,ti) ∈Rmは最後に選んだ関数fi-1と取引の履歴stiの特徴の表示である。5.1節でαのインスタンス化を行う。1）関数fiのサンプリング：Fの関数を（現在のtracetiも考慮して）特徴表現行列α（F,ti）∈R|F|×mに変換し、hiとα（F,ti）∈R|F|×mを生成する。そして、hiとα(F,ti)をsoftmaxFCNfunc:Rn×R|F|×m→[0,1]|F|の5層FCNに与える。これは図4のボックス[1]に示されている。直感的には, FCNfunccomは各関数に対して, 現在の状態からその重要性を表すスコアを計算する. このプロセスを要約すると、fi∼πnnfunc(ti)=FCNfunc(hi, α(F,ti)) となる。 πncangは最も重要な引数の種類である、整数(符号付き、符号なし、任意の幅)、アドレス、配列(静的、動的、任意の次元)を生成する。 次に、整数関数の生成方法について説明します。整数関数の生成には2つの課題があります。 第二に、関数は様々な数の整数引数を持つ。このため、我々はGRUを用いて生成過程を変更し、生成される引数の数は関数fiのアリティに基づく。図4のボックス[2]に示すように（引数が2つの場合）、j番目の整数intjを生成するために、最後に生成した整数OH(intj-1)と最後の整数生成状態hintj-1∈Rnをワンショット符号化してGRUintに与え、現在の状態hintj∈Rn：hintj=GRUint（OH（intj-1）, hintj-1)を取得する。 そして、FCNint:Rn→ [0,1]|S I| というソフトマックスを持つ2層FCNがhintjに作用し、intjをサンプリングした分布を生成する: intj∼FCNint(hintj) 初期状態hintinはファジング状態とし、初期入力はゼロベクトルとなる。 アドレス引数は可変長とすることも可能であり、GRUを用いて同様に生成される。 (3)Samplingsenderi 図4のボックス［3］に示すように、ソフトマックスを持つ3層FCN、FCNsender：Rn→［0，1］｜SND｜からsenderiをサンプリングする：senderi ∼πnnsender(ti)=FCNsender(hi). (4)amountiのサンプリング最後に、選択された関数fiが非支払関数であればamounti=0とする。そうでなければ、可能なエーテル量の集合に対する確率分布を計算する必要がある。図4のボックス[4]に示すように、3層FCN with softmaxFCNamount:Rn→[0,1]|SA| はSA上の確率分布を出力し、そこからamountiがサンプリングされる。上記の後、新しい取引を生成し、その取引を契約に対して実行し、隠れ状態を更新する。 ここでα(F,ti)は抽出された特徴表現、tiはステップiでシンボリック実行エキスパートによって生成された取引である。我々のエキスパートとそのようなデータセットの生成については5.2節で説明する。我々の目標は、πnnがDと同じトランザクションのシーケンスを生成するように訓練することである。Dの1つのシーケンスについて学習するために、そのトランザクションを再実行する。ステップiごとに、特徴量α(F,ti)と隠れ状態hi-1をπnnに与える。intiと同じ関数、引数、送り主、金額を選択する確率に基づいてクロスエントロピ損失を計算する。そして、tiを実行し、tiに基づくGRUの隠れ状態を更新する。一連の取引をすべて再実行した後、損失に対してバックプロパゲーションを行い、全ネットワークの重みを共同で更新する。標準では、シーケンスのバッチで学習し、全てのネットワークが高い分類精度に達した時点で停止する。

5 THE ILF SYSTEM

前述したニューラルネットファジングポリシーを実装したILFシステムを紹介する。まず、関数の特徴表現について紹介する。次に、学習データセットを生成するために使用される記号実行エキスパートについて説明する。最後に、ファジング中にスマートコントラクトの重大な脆弱性を検出することについて述べる。

5.1 Feature Representation of Functions

表2には、ニューラルネットワークの入力として使用する関数の意味的特徴が示されている。各特徴は与えられた関数fと取引履歴stに対して導出される。上位3つの特徴は、取引履歴stの最後の呼び出しtofとすべての呼び出しtofの成功に関する重要な情報を捕らえる。例えば、tofの最後の呼び出しを取り消した場合、またはfinの多くの呼び出しを取り消した場合、これはfの引数が関数fの事前条件に違反する可能性が高いことを示す。特徴Transactionはfを呼び出すトランザクションの割合を測定し、特徴Coveragは現在のコントラクトカバレッジとfを呼び出すことによって得られるカバレッジを捕捉する。FeatureOpcodesは、50個の特徴的なオペコードinfのカウントを含むベクトルを返し、機能性と複雑さを測定する。50個の特徴的なオペコードを選択するために、算術演算やスタック演算に使用されるような一般的なオペコードを除外した。50個のオペコードの一覧を付録Aに示す。FeatureNameは関数名を表す。この特徴量を得るために、fの名前をcamelCaseとpascal_caseにしたがってトークン化し、それぞれのサブトークンをWord2Vcword embedding [41]にマップする。特徴量Nは関数の意味（ゲッター、セッターなど）を捕捉する。これらの特徴量に基づき、テストされた契約Fの（公開および外部）関数と取引stの履歴から意味的な特徴行列αs（F、t）を抽出するαsを定義する。グラフ畳み込みネットワークによる埋め込み：関数間の依存性を捕らえるために、グラフ畳み込みネットワーク（GCN）［35］を採用する。ここで、Fの各関数はノードで表現され、エッジ(f,f′)はf′の読み込みと書き込みのセットが重複する（依存関係を示す）ことを捕らえるグラフдを構築する。このグラフを用いて、意味情報αs(F,t)を以下のように埋め込む： α(F,t)=GCN(αs(F,t),д)whereGCN:R|F|×l×G→R|F|×m は意味特徴行列を埋め込み行列に変換する。埋め込み行列α(F,t)は、4.2節で説明したようにπnnの入力として用いられる。GCNは入力特徴量αs(F,t)とπnnの間の中間層として扱われ、πnnと共同で学習されることに注意する。GCN の使用方法の詳細については、付録 B を参照されたい。

5.2 Symbolic Execution Expert

記号実行の拡張の課題：理想的な専門家は、複数のトランザクションを完全に記号的に分析し、高いカバレッジを達成する具体的なトランザクションの順序を選択することができます。具体的には、1つのトランザクションが初期ブロック状態binitから到達したすべての動作を完全に分析するために、契約を記号的に実行し（記号的トランザクションを仮定）、トランザクションの終了時に記号的状態を計算することができる。この結果、シンボリックブロック状態φ11(T1),…,φ1n(T1)が得られ、ここでT1 はシンボリックトランザクション、nis は契約中のパスの数で決定される。次に、2つのトランザクション内で到達できるすべての動作を分析するために、各シンボル状態φ1i（T1）から契約をシンボリックに実行し、シンボリックブロック状態φ21（T1，T2），…，φ2m（T1，T2）（T1およびT2は第1および第2のシンボリックトランザクション）をもたらす。このようなスキームは、分析されたシンボリックトランザクションの深さkまで続けることができる。残念ながら、上記のアプローチは、（セクション2.2で述べたように）その指数関数的時間複雑性のためにスケールしない。実際のスケーラビリティを測定するために、我々のデータセットから100個の小さい契約（<3K命令）と100個の大きい契約（≥3K命令）をランダムに選択した。そして、選択されたコントラクトのうち、異なる深さskに対して記号的実行（前述の通り）を用いて3日以内に解析できる数を測定しました。その結果を図5に示す．このデータから、1トランザクション内で到達可能なすべての状態に関する記号的推論が実行可能であることがわかる。このようなスケーラビリティの問題を考慮し、我々は実用的な記号的実行エキスパートπexpertを設計した。このエキスパートは、単一のトランザクションについて記号的に契約を実行し、カバレッジを最適化するために具体的なものを選択することにより、一連のトランザクションを繰り返し構築する。エキスパートポリシーπexpert(t)は、一連の具体的なトランザクションstが与えられたとき、現在の具体的なブロック状態（すなわち、tatbinitを実行したときに達したブロック状態）から契約を記号的に実行し、（もしあれば）最もカバレッジを改善する実行可能経路を選び、制約解消器を実行してその経路に従う具体的トランザクションを生成し、stを返す。現在のブロック状態でカバレッジを改善できるトランザクションがない場合、πexpert(t)=⊥となる。VerX [46]の記号実行エンジンを使用して、契約を記号的に実行し、トランザクションtを構築する。 アルゴリズム1では、エキスパートポリシーπexpertをターゲット契約cに対して実行するための手順を定義する。エントリ手順であるRunExpertは、エキスパートポリシーπexpertが与えられたブロック状態に対して新しいトランザクションを生成することによって達成できるカバレッジの改善によってランク付けした、観測したブロック状態に関する優先キューQを維持する。初期状態では、Qは初期ブロック状態binitを含む。ループの反復ごとに(Line 3)，RunExperはQからブロック状態bをポップし(Line 4)，DfsFuzzを実行する(Line 5) ，観測したブロック状態がカバレッジをさらに改善できなくなるまで（つまり，Qが空になるまで）．まず、この手続きは、現在のブロック状態に到達する具体的なトランザクションst=Txs(b)のシーケンスを取得し、エキスパートポリシーπexpert(t)を実行して、網羅性を改善するトランザクションtか⊥（トランザクションが網羅性を改善していないことを示す）のどちらかを返す。DfsFuzzはb′で再帰的に呼び出され、さらにcoverageを改善する可能性のある別のトランザクションを生成する。DfsFuzzによってカウントされたすべてのブロック状態bはQにプッシュされ、RunExpertが異なるトランザクションのシーケンスを生成するために再び考慮できるようになる。図6では、RunExpertの実行例を示している。まず、初期ブロック状態binitasを引数としてDfs-Fuzzが実行される。t1が実行され、ブロック状態b1へコントラクトを遷移させる。ブロック状態b1において、πexpertはcoverageを向上させる4つのパスを検討し、atest2を生成し、契約をb2に遷移させる。t1,t2,…はπexpertが生成するトランザクションのシーケンスに対応することに注意。さらに、Dfs-Fuzzは観測された全てのブロック状態binit, b1, b2,…を適用し、これらは全てRunExpertが異なるシーケンスを生成するために考慮する。 学習用のトランザクションシーケンス生成学習セットの各契約cdに対して、RunExpert（アルゴリズム1）を用いて特徴αsを追跡しながらトランザクションを生成させる。ここで、αs(F,ti)は特徴行列であり、tiはπexpertonbi-1（tiによって生成されるブロック状態）の実行によって生成される最も長いシーケンス[(αs(F,ti),ti)]dを選択します。これは通常、DfsFuzzが生成する最初のシーケンスである。次に、生成されたデータセットD=[(αs(F,ti),ti)]d|D|d=1が、セクション4.2で説明するπnnの学習に使用できる。 シード整数と量の学習セクション4.2で述べたように、シードの集合SIから整数引数をサンプリングする。この集合は、SMT制約のπexpertsolvingによって生成されたD内の最も頻繁に使われる 上位K個の整数を選択することによって構築される。種数SAも同様に構成される。SIとSAの例とその出現回数は付録Dに示す。

5.3 Vulnerability Detection

我々は、スマートコントラクトの重大な脆弱性を特定する6つの検出器を[32,42]から採用した。これらは、簡単な説明とともに表3に示され、付録Cでさらに詳しく説明されている。より多くの検出器を簡単に追加することができることに留意されたい。我々は、いくつかの検出器によって必要とされた、具体的な実行トレース上のバックワードスライシングに基づく高速データフロー解析を実装した。

6.1 Implementation

私たちのトランザクション実行バックエンドは GoEthereum[20]の上に実装されています。RPCコールを行う代わりに、ILFは高速実行を達成するためにネイティブにトランザクションを送信する。ニューラルネット（NN）はPytorch[2]を用いて実装されています。また、FCNは活性化関数としてReLUを使用している。ILFは5人の送信者(3人の信頼できるユーザと2人の攻撃者)を用いてファジングを行うが，実験ではこれで十分であった(送信者が多くてもファジングは改善されない)．種整数集合SIと種量集合SAのサイズを共に50に設定した(例を付録Dに示す)．ロック状態に陥るのを避けるため、πnnとπunifsoの実行時に、50取引ごとにブロックチェーンを初期ブロック状態に戻すヒューリスティックが追加された。

6.2 Evaluation

ベースライン：この実験では，ILFを表4に示すベースラインおよび既存のツールと比較する．UnifとExpertはそれぞれπunifとπexpertのファジングポリシーを使用し、Echidna[17]はカバレッジを報告するが検出器を実装していない。 データセット：Etherscan verifiedcontracts [19]（Ethereumメインネットに展開された実世界の契約）をクロールすることでデータセットを取得する．また、デプロイに失敗したコントラクトや、データセットに存在しないコントラクトへのハードコードされたアドレスを含むコントラクトをフィルタリングしました。最終的なデータセットには、18,496件のコントラクトが含まれています。異なるサイズのコントラクトのカバレッジを調べるために、データセットを5,013個の大きなコントラクト（≧3K命令）と13,483個の小さなコントラクト（<3K命令）に分割しました。表 5 にデータセットの統計量を示す。ターゲットコントラクトと相互作用することができるコントラクト（もしあれば）をローカルテストブロックチェーンに追加していることに留意されたい。これらのコントラクトは、ターゲットコントラクトのコンストラクタ引数によって識別される。

実験.実験では、標準的な5重クロスバリデーションを行った。512GBのメモリと2.2GHzのAMDYC7601CPU（64コア、128スレッド）を搭載したサーバでExpert（各契約に3時間制限）とContract-Fuzzerを実行し、データセット全体を実行するのに76時間、ContractFuzzerは62時間（大規模並列化時）かかりました。その他の実験は、64GBメモリ、4.2GHz Intel Core i7-7700KCPU（8コア8スレッド）1個、Geforce GTX 1080 GPU 2個を搭載したデスクトップで実施しました。

6.3 Code Coverage

カバレッジの評価結果について説明する．測定対象は命令カバレッジと基本ブロックカバレッジである。本節では、命令カバレッジについて報告する。基本ブロックカバレッジの結果は同様であり、付録Eに記載されています。以下では，まずILFとファザ(UnifおよびEchidna)を比較し，次にExpertを比較する．ILFはUnifとEchidnaを常に凌駕している．小さい契約では、ILFは94%のカバレッジを達成し、Unifより16%、Echidnaより24%高い。Echidnaは、EVMのモデルが不完全であり（例えば、送信者が1人であり、msg.valueをモデル化していない）、811契約においてエラーで終了した（カバレッジ0%を報告）ため、良い結果を得ることができなかった。なお、4.3%の契約については、結果に大きな影響を与えることはない。全体として，ILF，Unif，Echidnaは高速であり，1Kトランザクションをファジングするために，1契約あたりそれぞれ平均7秒，4秒，6秒を費やした． 図9では，ILFとExpert(ILFはExpertを模倣していることがわかる)を比較している．Expertは、平均して30回のトランザクションを費やして、小さなとなった。同じトランザクション数の場合、Expertと比較して、ILFは小さい契約では8%、大きい契約では11%低いカバレッジを達成した。しかし、Expertの処理速度は遅く、Expertが図9のカバレッジを達成するのに平均547秒（小さい契約）、2580秒（大きい契約）かかっています。また、ILFを2Kトランザクションで実行しました（小口契約では13秒、大口契約では17秒を費やしただけです）。この場合、ILFはExpertを小契約で4%、大契約で19%上回った。大口契約ではExpertのタイムアウトが多くなり、カバレッジが低下することがわかった。このことから、ILFはExpertよりもトランザクションの生成速度が桁違いに速く、Expertよりも多くのコードを適度な時間でカバーできる利点があることがわかります。

6.4 Vulnerability Detection

我々は，ILF，Unif，Maian，ContractFuzzer を実行し，データセットの脆弱性を検出した．まず，これらのツールを実行するためのセットアップを説明し，その速度を報告する．次に，脆弱性のグランドトゥルースをどのように取得するかを説明する．最後に，脆弱性検出についてILFと各ツールを比較する． Setup and Speed. ILFとUnifranは，各契約の2Kトランザクションに対して，それぞれ平均14sと8sを費やした．Maiandは、各脆弱性を個別に検出する。Maiandは各脆弱性を分割して検出し、各契約のLeaking, Suicidal, Lockingを検出するのに平均61秒、15秒、13秒（デフォルト深度3）かかりました。ContractFuzzerはUnhandled ExceptionとControlledDelegatecallに対してのみ真陽性となるが、Block Dependencyに対しては偽陽性となる可能性がある。各システムが発見したすべての真の脆弱性の和をグランドトゥルースとし，各システムの割合（グランドトゥルースに対する割合）を報告する．図10はその結果を示しており、ILFはすべての種類の脆弱性において、他のすべてのシステムを上回っていることがわかります。 Comparing ILF to Uniformly Random Baseline ILFはUnifよりもLeaking, Block Dependency, UnhandledExceptionの脆弱性を平均43%多く発見しています。また，他の脆弱性についても，Suicidalで15%，Lockingで22%，Controlled Delegatecallで6%向上しています．

  • Leaking
  • Block Dependency
  • Unhandled Exception
  • Suicidal
  • Locking
  • Controlled Delegatecall

ComparingILFto a Symbolic Execution Detector. ILFはMaianと比較して，Leaking脆弱性を43%多く検出しています．この結果から、Maianの偽陰性はほとんどが(i)それらのコントラクトにエーテルを送れなかったか、(ii)脆弱性をトリガーするのに必要な深さの手前で停止したためであることがわかる。ILFはMaianよりも18%多くLockingの脆弱性を検出し，Maianは80のLockingの報告のうち29を偽陽性とした．ILFはContractFuzzerと比較して、全体的に多くの脆弱性を発見しています。これは，ContractFuzzerがランダムに生成するトランザクションが，学習した戦略を使用してコードを探索するILFとは異なり，脆弱なコードをカバーできないためと考えられる．ContractFuzzerの検出ルールは，トレースにイーサ転送とブロックステート変数が存在するかを構文的にチェックするが，ILFではセマンティックデータフローチェックを行うため，ブロック依存性で6件の偽陽性を生成している．

9 Conclusion

我々は、symbolicexecutionからファザーを学習するための新しいアプローチを提示し、スマートコントラクトのドメインにそれをインスタンス化しました。重要なアイデアは、ニューラルネットワークを使用して表現されるファジングポリシーを学習することであり、これは、シンボリック実行エキスパートを使用して生成された入力の高品質データセット上で学習される。学習されたポリシーは、未見のスマートコントラクトをファジングするための入力を生成するために使用される。我々はこの方法をILFと呼ばれるシステムに実装し、実世界の契約において高速かつ高いコードカバレッジを達成することを示した。高いカバレッジは重大な脆弱性の検出を容易にし向上させ、既存のツールを凌駕する。

グラフビュー