学習コースLearn

プログラム解析

プログラムを実行せずに、あるいは実行しながら解析し、コードの構造・品質・振る舞いを読み解く技術を、概要から理論、そして実際に動かせるコードまで、順を追って学ぶモジュールです。各ステップは「概要 → 仕組み（座学）→ コードで動かす」の3層で進みます。ページ内には手を動かせるデモを3つ用意しました。

この教材は日本語のみで提供していますThis learning material is available in Japanese only.

学びはじめるStart learning まず手を動かす（構文木デモ）Jump to the syntax-tree demo

はじめにIntroduction

このモジュールの全体像

プログラム解析（program analysis）とは、ソースコードやプログラムそのものを対象に、その構造・品質・振る舞いを機械的に読み解く技術の総称です。コンパイラの最適化、統合開発環境（IDE）のエラー表示や補完、リンタによるスタイル指摘、セキュリティ検査、そしてリファクタリング支援まで、私たちが日々使う開発ツールの多くが、この技術の上に成り立っています。

プログラム解析には大きく2つの立場があります。プログラムを実行せずにコードそのものから性質を調べる静的解析と、実際に実行してその様子を観測する動的解析です。どちらの場合も、まず生のソースコードを機械が扱える構造へ変換することから始まります。次のような流れ（パイプライン）が基本です。

プログラム解析の基本パイプライン

ソースコード Source code 構文解析（AST） Parse 解析 Analyze 結果 Result 字句解析・構文木 静的解析・動的解析 指標・警告・クローン

このモジュールは、上のパイプラインを左から順にたどります。各ステップは次の3層で構成します。

  • 概要：その技術が何のためにあるのか、あらましをつかむ。
  • 仕組み（座学）：背後にある考え方・定義・式を、ていねいに理解する。
  • コードで動かす：Python の標準ライブラリや定番ツール、ページ内デモで実際に動かして確かめる。

手を動かす題材には、特別なデータは使いません。Python の標準ライブラリのソースや任意の公開 Python コード、そしてページ内の小さなコード片やサンプルだけを使います。特別な環境がなくても、読みながら試せる構成です。

1

プログラム解析とは

What is program analysis

概要Overview

プログラム解析は「プログラムについて、プログラムで調べる」技術です。人が目で追うには大きすぎるコードから、機械的に情報を引き出します。おもな用途を挙げます。

  • バグ発見：未定義の変数、到達しないコード、型の不一致などを、実行前に見つける。
  • 品質評価：複雑さや重複を数値化し、保守しにくい箇所を可視化する。
  • セキュリティ：外部入力が危険な場所に届く経路（脆弱性）を検出する。
  • リファクタリング支援：安全に名前を変える、関数を抽出する、といった変換を機械的に助ける。
  • 最適化：コンパイラが、意味を変えずに速く・小さくコードを書き換える。

仕組みHow it works

解析には、実行するかどうかで大きく2つの立場があります。

静的解析（static analysis）

プログラムを実行せずに、ソースコードやコンパイル後のバイトコードそのものを調べます。あらゆる入力・あらゆる経路を（近似的に）まとめて扱えるのが強みです。いっぽう、実行時にしか決まらない値（利用者の入力やファイルの中身など）は分からないため、結果はどうしても近似になります。安全側に倒すと、実際には問題ない箇所まで警告する偽陽性が増えがちです。

動的解析（dynamic analysis）

プログラムを実際に実行して、その振る舞いを観測します。実行した具体的な値や経路について正確な情報が得られます。ただし、観測できるのは実行した経路だけで、試さなかった入力の挙動は分かりません。見逃し（偽陰性）が起きやすいのが弱点です。テストカバレッジやプロファイリングが代表例です。

解析の限界

「このプログラムは必ず停止するか」「この2つのプログラムは同じ振る舞いか」といった、プログラムの意味に関する非自明な性質は、一般には機械的に完全に判定できないことが知られています（ライスの定理・停止性問題）。だからこそ実務の解析は、安全な近似・ヒューリスティック・限定した範囲での判定を組み合わせて、役に立つ答えを返すよう設計されています。静的と動的は対立するものではなく、互いの弱点を補い合う道具だと考えるのがよいでしょう。

この Step のまとめ

プログラム解析はコードから機械的に情報を引き出す技術。実行しない静的解析は網羅的だが近似的、実行する動的解析は正確だが観測した経路だけ。両者を組み合わせて、バグ発見・品質評価・セキュリティに役立てます。

2

字句・構文解析とAST

Lexing, parsing & the AST

概要Overview

コードを解析する第一歩は、ただの文字の並びを構造に変えることです。人間が「2 + 3 * 4」を見て「掛け算が先」と読み取るように、機械にも文の骨組みを理解させます。この骨組みが抽象構文木（AST: Abstract Syntax Tree）で、ほとんどの解析はこの木の上で行われます。

仕組みHow it works

1. 字句解析（lexing / tokenization）

文字列を、意味のある最小単位であるトークンに区切ります。y = 2 + 3 なら、y（識別子）・=（記号）・2（数値）・+（記号）・3（数値）に分けます。空白やコメントはここで落とします。Python では標準ライブラリ tokenize がこの役目を担います。

2. 構文解析（parsing）

トークンの並びを、文法規則に従って木に組み立てます。ここで演算子の優先順位と結合性が効きます。2 + 3 * 4 では、掛け算が足し算より優先されるので、3 * 4 がひとつのまとまりになり、その結果と 2 を足す、という入れ子の木になります。同じ優先順位の 10 - 4 - 2 は左から結合し、(10 - 4) - 2 と解釈されます。

3. 抽象構文木（AST）

できあがった木からは、括弧やセミコロンといった「書き方の飾り」を落とし、構造の本質だけを残します。これが AST です。各ノードは「代入」「二項演算」「関数呼び出し」などの構文要素に対応します。木になっていれば、深さ優先でたどって特定のパターンを探す、といった処理が素直に書けます。

なお、Python はソースをバイトコードにコンパイルしてから仮想マシンで実行します。標準ライブラリ dis を使うと、この中間表現（どんな命令に落ちるか）を覗くことができます。字句解析・構文解析・AST は、その手前の「意味を組み立てる」段階だと考えるとよいでしょう。

デモ 1Demo 1

式の構文木

算術式（+ - * / と括弧、整数）を入力すると、簡易パーサが演算子の優先順位に従って構文木を組み立て、SVG のツリーで表示します。掛け算・割り算は足し算・引き算より先に、括弧が最優先です。木の下には、その優先順位で計算した結果も表示します。

例

コードで動かすRun the code

まず字句解析です。標準ライブラリ tokenize で、文字列がどんなトークンに分かれるかを見てみます。

Pythonlex_tokenize.py
import tokenize, io

src = "y = 2 + 3 * 4\n"
for tok in tokenize.generate_tokens(io.StringIO(src).readline):
    if tok.string.strip():          # 空白・改行トークンは省く
        print(tokenize.tok_name[tok.type], repr(tok.string))
出力例 / Output
NAME 'y'
OP '='
NUMBER '2'
OP '+'
NUMBER '3'
OP '*'
NUMBER '4'

次に構文解析です。標準ライブラリ ast の ast.parse でソースを AST に変換し、ast.dump で構造を文字列にして眺めます。2 + 3 * 4 が、掛け算を内側に持つ入れ子の BinOp になっている点に注目してください。

Pythonast_dump.py
import ast

tree = ast.parse("y = 2 + 3 * 4")
print(ast.dump(tree, indent=2))
出力例 / Output
Module(
  body=[
    Assign(
      targets=[
        Name(id='y', ctx=Store())],
      value=BinOp(
        left=Constant(value=2),
        op=Add(),
        right=BinOp(
          left=Constant(value=3),
          op=Mult(),
          right=Constant(value=4))))],
  type_ignores=[])

ast.walk を使うと、木のすべてのノードを順にたどれます。ここでは二項演算（BinOp）のノードだけを拾い、その演算子の種類を表示してみます。

Pythonast_walk.py
import ast

tree = ast.parse("y = 2 + 3 * 4")
for node in ast.walk(tree):
    if isinstance(node, ast.BinOp):
        print(type(node.op).__name__)
出力例 / Output
Add
Mult

この Step のまとめ

解析は「文字列 → トークン → 構文木（AST）」という変換から始まります。演算子の優先順位はこの木の形に現れます。Python では tokenize で字句解析、ast で構文解析ができ、以降の解析はすべてこの木の上で行われます。

3

静的解析

Static analysis

概要Overview

AST が手に入れば、プログラムを実行せずにさまざまな性質を調べられます。これが静的解析です。処理の流れ（制御フロー）やデータの流れ（データフロー）を追い、あやしい箇所を機械的に指摘します。リンタや型検査器、IDE の警告は、みなこの技術の応用です。

仕組みHow it works

制御フローグラフ（CFG）

プログラムの「どこからどこへ進みうるか」をグラフで表したものが制御フローグラフ（Control Flow Graph）です。分岐のない一続きの命令列を基本ブロックとしてノードにまとめ、条件分岐やループによる遷移をエッジで結びます。「この行に到達できるか」「ここから抜け出せるか」といった問いは、このグラフ上の到達可能性の問題になります。

データフロー解析

変数の値がプログラム中をどう流れるかを追うのがデータフロー解析です。ある地点で「どの代入の結果が生きているか（到達定義）」「この先で使われる変数はどれか（生存変数）」などを、CFG に沿って伝播させて求めます。応用として、定義・使用連鎖（def-use chain）を作れば、「代入したのに一度も使われない変数」や「使う前に値が入っていない変数」を検出できます。

リンタの仕組み

リンタ（linter）は、AST を走査してあらかじめ決めたパターン（アンチパターン）に一致する箇所を警告するツールです。未使用の変数・インポート、比較演算子の誤用、命名規約からの逸脱などを指摘します。Python では pylint や flake8 が定番で、内部では ast のような構文木の走査を行っています。次のコードは、その「未使用変数の検出」を ast だけでミニチュア実装した例です。

Pythonunused_vars.py
import ast

source = '''
def f(x):
    y = x + 1
    z = x * 2      # z は使われない
    return y
'''

fn = ast.parse(source).body[0]          # 関数定義ノード
assigned, used = set(), set()
for node in ast.walk(fn):
    if isinstance(node, ast.Name):
        if isinstance(node.ctx, ast.Store):    # 代入されている名前
            assigned.add(node.id)
        elif isinstance(node.ctx, ast.Load):  # 読み出されている名前
            used.add(node.id)

print("assigned:", sorted(assigned))
print("used:    ", sorted(used))
print("unused:  ", sorted(assigned - used))
出力例 / Output
assigned: ['y', 'z']
used:     ['x', 'y']
unused:   ['z']

ノードの ctx（コンテキスト）が Store なら代入、Load なら読み出しです。代入された名前の集合から使われた名前の集合を引けば、「代入したのに使われていない」変数が求まります。これは静的解析の考え方そのもので、本物のリンタは、これにスコープや制御フローの情報を加えて精度を高めています。

この Step のまとめ

静的解析は AST の上で、制御フロー（CFG）とデータフローを追う技術です。定義・使用の関係を調べれば、未使用変数のような問題を実行前に見つけられます。pylint や flake8 は、この考え方を体系化したツールです。

4

コードメトリクスと品質

Code metrics & quality

概要Overview

「このコードは複雑すぎないか」「テストしにくくないか」を、感覚ではなく数字で語るための道具がコードメトリクスです。規模・複雑さ・重複などを測り、保守しにくい箇所を客観的に浮かび上がらせます。品質のすべてを数字で表せるわけではありませんが、注意を向けるべき場所の目印になります。

仕組みHow it works

行数（LOC）

もっとも素朴な指標が行数（Lines of Code）です。空行やコメントを除いた実行文の行数（論理行数）を数えるのが一般的です。単純ですが、規模の当たりをつけるのに役立ちます。

循環的複雑度（cyclomatic complexity）

McCabe が提案した循環的複雑度は、制御フローグラフをもとに「独立した経路の数」を測る指標です。分岐が多いほど値が大きく、テストすべき経路も増えます。CFG のエッジ数を E、ノード数を N、連結成分の数を P とすると、次の式で定義されます。

M = E - N + 2P E: 制御フローグラフのエッジ数　N: ノード数　P: 連結成分の数（1つの関数なら P = 1）
これは、判定点（if・for・while・and・or・case など）が d 個ある構造化プログラムでは M = d + 1 と一致します。

実務では、この「判定点を数えて 1 を足す」やり方で手早く見積もります。分岐が 0 なら M = 1（一本道）、分岐が増えるほど M も増えます。目安として、M が小さいほど理解・テストしやすく、大きくなるほど分割を検討する合図になります。次のデモは、まさにこの数え方で複雑度を計算します。

その他の指標

  • Halstead 指標：コード中の演算子・オペランドの種類数と総数から、プログラムの語彙・規模・難しさ（difficulty）・労力（effort）などを見積もる。
  • 保守性指数（Maintainability Index）：Halstead 体積・循環的複雑度・行数を組み合わせ、保守のしやすさを一つの数値にまとめたもの。
  • コードスメル：長すぎる関数、巨大なクラス、重複コードなど、設計上の「におい」。バグそのものではないが、改善の候補。
  • コードクローン：コピー＆ペーストなどで生まれた、よく似たコード片。片方を直すともう片方が直し忘れられる、といったリスクの温床（Step 5 で検出を体験します）。
デモ 2Demo 2

循環的複雑度

疑似コード（Python 風）を入力すると、if・elif・for・while・case・and・or（&&・|| も）といった判定点を数え、循環的複雑度 M = 判定数 + 1 を計算します。内訳の表と、簡単・やや複雑・複雑の目安も表示します。

例

コードで動かすRun the code

Python では radon が定番です。次の example.py（先ほどの grade 関数）を測ってみます。この関数は if と elif が2つ、合わせて判定点が3つなので、複雑度は M = 3 + 1 = 4 です。コマンドラインの radon cc で確認します。

Shellradon_cc.sh
# pip install radon
$ radon cc example.py -s
出力例 / Output
example.py
    F 1:0 grade - A (4)

F は関数（Function）、1:0 は行:列、grade は名前、A はランク、(4) が循環的複雑度です。radon はランクを A（1〜5）から F（41 以上）で表します。同じことを Python から行うには radon.complexity.cc_visit を使います。

Pythonradon_api.py
from radon.complexity import cc_visit

source = open("example.py").read()
for block in cc_visit(source):
    print(block.name, block.complexity)
出力例 / Output
grade 4

この Step のまとめ

コードメトリクスは品質を数値化する道具。循環的複雑度は M = E - N + 2P（判定点 + 1）で分岐の多さを測ります。radon の cc で簡単に計測でき、テストしにくい複雑な関数の目印になります。

5

動的解析

Dynamic analysis

概要Overview

ここまでは実行せずに調べる静的解析でした。いっぽう動的解析は、プログラムを実際に動かして、その様子を観測します。「どの行が実行されたか」「どこで時間がかかったか」といった、実行時にしか分からない情報が得られます。テストカバレッジ・プロファイリング・トレースが代表的な道具です。

仕組みHow it works

テストカバレッジ

カバレッジは、テストがコードのどれだけを実行したかを測る指標です。行カバレッジは実行された行の割合、分岐カバレッジは条件分岐の真・偽の両方を通ったかを見ます。カバレッジが低い箇所は「テストで一度も動かしていない場所」であり、バグが潜みやすい要注意ゾーンです。Python では coverage.py が定番です。

プロファイリング

プロファイリングは、どの関数がどれだけ呼ばれ、どれだけ時間を使ったかを計測します。「速くしたい」ときに、当てずっぽうで直すのではなく、実測にもとづいてボトルネックを特定するために使います。Python 標準の cProfile が手軽です。

トレースと限界

トレースは、実行の経路や関数の呼び出し順を時系列で記録します。動的解析に共通する限界は、観測できるのは実際に実行した経路だけという点です。与えた入力しだいで結果が変わるため、静的解析のような網羅性はありません。だからこそ、両者を組み合わせるのが実務の基本になります。

コードで動かすRun the code

まずカバレッジです。テストを coverage 経由で実行し、レポートを出します。-m を付けると、実行されなかった行番号（Missing）も表示されます。

Shellcoverage.sh
# pip install coverage
$ coverage run -m pytest
$ coverage report -m
出力例 / Output
Name          Stmts   Miss  Cover   Missing
-------------------------------------------
mymodule.py      20      3    85%   12-14
-------------------------------------------
TOTAL            20      3    85%

全 20 文のうち 3 文（12〜14 行目）が未実行で、行カバレッジは 85% です。次はプロファイリングです。cProfile.run に測りたい処理を渡します。

Pythonprofile_example.py
import cProfile

def slow():
    return sum(i * i for i in range(100000))

cProfile.run("slow()")
出力例 / Output
         100005 function calls in 0.012 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.011    0.011 profile_example.py:3(slow)
   100001    0.005    0.000    0.005    0.000 profile_example.py:4(<genexpr>)
        1    0.000    0.000    0.012    0.012 {built-in method builtins.exec}
        1    0.005    0.005    0.010    0.010 {built-in method builtins.sum}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

ジェネレータ式が 100001 回呼ばれ（10 万個の値と、最後の停止で 1 回）、そこと sum に時間が集中しているのが読み取れます。どこを直せば速くなるかが、実測から分かります。

実践：コードの重複を測る（クローン検出）

最後に、品質評価の実践としてコードクローン検出を体験します。これはコードを実行せずトークン列を比べる手法ですが、コピー＆ペーストで増えた重複を見つけ、保守性の問題を洗い出すのに使われます。よくある手法は、コードを正規化してトークン列にし、その類似度を測るものです。空白やコメントを無視するだけの一致（Type-1）に加え、変数名や定数の違いを吸収すると、名前だけ変えた複製（Type-2）も見つかります。次のデモは、正規化したトークンの並びから類似度を計算します。

デモ 3Demo 3

コードクローン検出

2つのコード片を入力すると、空白とコメントを除き、変数名を ID・数値を NUM・文字列を STR に正規化してトークン列にします。トークンの2-gram（隣り合う2つ組）の集合どうしの Jaccard 係数で類似度を測り、クローンかどうかを判定します。Jaccard = |共通| / |和集合| です。

例

この Step のまとめ

動的解析は、実行して観測する技術です。coverage でテストの網羅度を、cProfile で性能のボトルネックを測れます。観測できるのは通った経路だけという限界を、静的解析が補います。トークンを正規化して比べれば、コードクローンも検出できます。

6

応用とこれから

Applications & what comes next

概要Overview

ここまでで、構文解析・静的解析・メトリクス・動的解析という基本の道具がそろいました。これらは単独でも役立ちますが、組み合わせると、より実践的な課題に応用できます。最後に、その広がりと、この先の学びへの橋渡しを見ておきましょう。

仕組みHow it works

バグ検出と欠陥予測

静的解析のパターン照合で「ぬるぽ（null 参照）になりうる」「例外が握りつぶされている」といった典型的な欠陥を見つけられます。さらに、過去の変更履歴やメトリクスを組み合わせ、どのファイルがバグを含みやすいかを見積もる欠陥予測という研究分野もあります。

セキュリティ解析

脆弱性を見つける解析には、コードを実行せず調べるSAST（静的アプリケーションセキュリティテスト）と、動かして試すDAST（動的〜）があります。中核となる考え方の一つがテイント解析で、外部からの入力（汚染源）が、データベース問い合わせやコマンド実行などの危険な地点（シンク）まで、無害化されずに届く経路を追跡します。

コードへの機械学習

近年は、コードをデータとして機械学習にかける流れが広がっています。AST やトークン列を数値ベクトルに変換するコード表現・埋め込みを作り、バグ検出・コード補完・要約などに使います。テキストを数値にする自然言語処理の発想が、そのままコードにも応用されているのです。ここは、このコースの機械学習・大規模言語モデル（LLM）のモジュールへとつながっていきます。

この Step のまとめ

基本の道具は、バグ検出・欠陥予測・セキュリティ解析（SAST/DAST・テイント解析）へ応用できます。さらにコードを機械学習の対象とみなす流れが、コード表現・埋め込みを通じて機械学習や LLM のモジュールへつながります。

まとめWrap-up

学びの振り返りと、さらに学ぶために

このモジュールでは、プログラムを読み解く基本の道具を、パイプラインに沿って順に手に入れました。

  • 構文解析とAST：文字列をトークンに区切り、優先順位を反映した構文木に組み立てる。
  • 静的解析：実行せずに制御フロー・データフローを追い、未使用変数などを見つける。
  • コードメトリクス：循環的複雑度などで複雑さ・品質を数値化する。
  • 動的解析：実行して観測し、カバレッジやプロファイルを測る。
  • 応用：バグ検出・セキュリティ解析、そしてコードへの機械学習へ。

次に進むなら、下の道具と資料が役に立ちます。

解析の対象・データ

  • 任意の公開 Python ソース：手元のスクリプトや OSS のコードをそのまま解析対象にできる。
  • Python 標準ライブラリのコード：ast や tokenize で読み込み、実在するコードで練習できる。

ライブラリ・ツール

  • Python 標準 ast・dis・tokenize：構文木・バイトコード・トークン列。
  • radon：循環的複雑度・保守性指数などの計測。
  • coverage：テストカバレッジの計測。
  • pylint / flake8：静的解析にもとづくリンタ。
  • tree-sitter：多言語対応の高速な構文解析ライブラリ。

参考書

  • Aho ほか『コンパイラ 原理・技法・ツール』（通称ドラゴンブック）
  • Nielson ほか『Principles of Program Analysis』
  • Møller, Schwartzbach『Static Program Analysis』（公開講義ノート）

次のモジュールへ

おつかれさまでした

ここで学んだ「コードを構造にして、静的・動的に調べる」という流れは、言語や規模を問わず通用する考え方です。手元の Python ファイルを題材に、3 つのデモを動かしてみてください。式を変え、疑似コードの分岐を増やし、コードを少しずつ書き換えると、構文木・複雑度・類似度がどう変わるかを確かめられ、理解がぐっと深まります。

発展トピックBeyond this module

このコースでは扱わない、関係する発展トピック

このモジュールでは、コードを構造にして静的・動的に調べる「基礎の流れ」を扱いました。いっぽうでプログラム解析は、より厳密な理論から最新の機械学習まで、幅広く発展しています。ここでは、このコースでは踏み込まないものの、知っておくと視野が広がる発展的なトピックを紹介します。深掘りは各自の興味に合わせてどうぞ。

高度な静的解析

  • 記号実行（symbolic execution）：変数を具体値ではなく記号のまま実行し、どんな入力でどの経路を通るかを論理的に解く。
  • 抽象解釈（abstract interpretation）：値を「符号」「区間」などの抽象領域で近似し、健全に性質を証明する理論的枠組み。

セキュリティと検証

  • テイント解析：外部入力が危険な地点に届く経路を追跡し、脆弱性を見つける。
  • ファジング（fuzzing）：大量のランダム・変異入力を与えてクラッシュを探す動的手法。
  • 形式検証：仕様に対する正しさを、モデル検査や定理証明で数学的に確かめる。

コードの機械学習

  • コード表現学習：AST やトークン列を数値ベクトルに変換する（code2vec など）。
  • 事前学習モデル：大量のコードで学習したモデル（CodeBERT など）を、バグ検出や要約に応用する。

生成と合成

  • プログラム合成：入出力例や仕様から、条件を満たすプログラムを自動生成する。
  • LLM によるコード生成・解析：大規模言語モデルがコードを書き、説明し、レビューを支援する最新の広がり。大規模言語モデル（LLM）のモジュールで扱います。