2026-03-13T04:50:06Z https://mie-u.repo.nii.ac.jp/oai

oai:mie-u.repo.nii.ac.jp:00009152 2023-09-11T01:43:48Z 366:640:641:647

プログラムの制御フローを考慮した値範囲解析 廣苅, 直人 山田, 俊行 application/pdf 現在，ソフトウェアは様々な分野で利用されているため，ソフトウェアの信頼性や安全性を向上させること，実行効率の良いソフトウェアを開発することが求められている．これらを実現するために，プログラム解析に関する研究が盛んに行われている．プログラム解析の1つである値範囲解析とは，プログラム中の各変数が取り得る値の範囲を解析することである．値範囲解析の結果を利用することで，ソフトウェアの脆弱性を検出できたり，プログラムを最適化できたりする．ソフトウェアは大規模化，複雑化が進んでいるため，解析結果の正確さが脆弱性の検出や最適化の結果に与える影響と解析に要する時間は無視できるものではなく，解析結果がより正確で，解析に要する時間がより小さい自動解析手法が求められている．Su らの手法[SW05] は，プログラム実行前に値範囲解析を行う．一般に，プログラム実行前の値範囲解析で完全な解析結果を求めることは不可能である．Su らの手法は，まずプログラム中の代入文から各変数が取り得る値の範囲が満たすべき条件を求める．そして，その条件から各変数が取り得る値の範囲を計算する．しかし，Su らの手法は制御フローを無視するため，実際のプログラムの実行では取り得ない範囲が解析結果に現れることがある．Su らの手法の解析結果はプログラム全体の制御構造を１つの無限ループに変換した時の解析結果と等しくなる．本研究は，Su らの手法よりも元のプログラムの制御構造を反映した制御構造に変換し，Suらの手法を一般化した値範囲解析アルゴリズムを提案する．制御構造の変換は，順次構造や分岐構造を残し，多重ループを単一のループに変換する．分岐構造やくり返し構造に非決定性を導入することによって，変換前のプログラムにおける代入文の実行系列を変換後のプログラムで再現できるため，この変換に対する正当性が保証される．Su らの手法はプログラム全体に対して値範囲解析アルゴリズムを適用する．提案手法は，プログラムをいくつかに分割し，それぞれに対して，Su らの手法を適用し，その結果を制御フローに従って伝播させる．したがって，提案手法は，Su らの手法と異なり，一部の制御フローを考慮できるため，解析結果がSu らの手法よりも正確になる．さらに，プログラム中の代入文の総数が変化しないため，時間計算量はSu らの手法の時間計算量と等しい． 三重大学大学院工学研究科博士前期課程情報工学専攻 1, 39 三重大学 2011-01-01 jpn thesis VoR http://hdl.handle.net/10076/12798 https://mie-u.repo.nii.ac.jp/records/9152 https://mie-u.repo.nii.ac.jp/record/9152/files/2010M243.pdf application/pdf 266.3 kB 2017-02-20