ソフトウェア・インテグリティ

 

Pythonバイトコードの知識

この記事では、筆者が最近Pythonのバイトコードを使用した経験をご紹介したいと思います。正確には、使用したのは専らCPythonインタープリタ向けのバイトコードで、バージョンは2.6と2.7に限定されていました。

Pythonは柔軟性の高い言語で、コマンドラインから実行すると主に次のステップをトリガします。

  • ソースコードは最初に検出されたとき(モジュールとしてインポートされたとき、直接実行されたときなど)にコンパイルされます。このステップで、システムに応じてpycまたはpyo拡張子が付いたバイナリ・ファイルが生成されます。
  • インタープリタがバイナリ・ファイルを読み取り、一度に1つずつ命令(命令コード)を実行します。

Pythonのインタープリタはスタックベースであるため、そのデータフローを理解するには各命令(命令コードと引数)がスタックに与える影響を知る必要があります。

Pythonのバイナリ・ファイルの検査

バイナリ・ファイルのバイトコードを取得する最も簡単な方法は、次のようにCodeTypeの構造体をアンマーシャルすることです。

import marshal
fd = open('path/to/my.pyc', 'rb')
magic = fd.read(4) # python version specific magic num
date = fd.read(4)  # compilation date
code_object = marshal.load(fd)
fd.close()

code_objectには、読み込まれたファイルのモジュール全体を表現するCodeTypeオブジェクトが格納されます。このモジュールのすべてのネストしたコード・オブジェクト(クラス宣言やメソッドなど)を検査するには、次のようにCodeTypeのコンスタントプールの検査を反復処理する必要があります。

import types

def inspect_code_object(co_obj, indent=''):
  print indent, "%s(lineno:%d)" % (co_obj.co_name, co_obj.co_firstlineno)
  for c in co_obj.co_consts:
    if isinstance(c, types.CodeType):
      inspect_code_object(c, indent + '  ')

inspect_code_object(code_object) # We resume from the previous snippet

この場合、各親の下でネストしているコード・オブジェクトのツリーが出力されます。次の単純なコードを実行してみましょう。

class A:
  def __init__(self):
    pass
  def __repr__(self):
    return 'A()'
a = A()
print a

次のようなツリーが得られます。

 <module>(lineno:2)
   A(lineno:2)
     __init__(lineno:3)
     __repr__(lineno:5)

テストのため、compileディレクティブを使用してPythonのソースコードを含む文字列からコード・オブジェクトを取得してみましょう。

co_obj = compile(python_source_code, '<string>', 'exec')

コード・オブジェクトの検査の詳細については、Pythonのドキュメントでco_*フィールドを参照してください。

バイトコードを一覧する

コード・オブジェクトを取得したら、実際にその(co_codeフィールド内の)逆アセンブルを見ていきましょう。バイトコードを解析して理解することには次の意図があります。

  • 命令コードの意味を解釈する
  • 引数を間接参照する

disモジュールのdisassemble関数を実行すると、その方法が示されます。これにより、前述のコード例からの次の出力が得られます。

2   0 LOAD_CONST        0 ('A')
    3 LOAD_CONST        3 (())
    6 LOAD_CONST        1 (<code object A at 0x42424242, file "<string>", line 2>)
    9 MAKE_FUNCTION     0
   12 CALL_FUNCTION     0
   15 BUILD_CLASS
   16 STORE_NAME        0 (A)

8  19 LOAD_NAME         0 (A)
   22 CALL_FUNCTION     0
   25 STORE_NAME        1 (a)

9  28 LOAD_NAME         1 (a)
   31 PRINT_ITEM
   32 PRINT_NEWLINE
   33 LOAD_CONST        2 (None)
   36 RETURN_VALUE

これで以下の情報が取得されます。

  • 行番号(変更されている場合)
  • 命令のインデックス
  • 現在の命令の命令コード
  • 実際の引数に解決するために命令コード(opcode)が取得する引数(oparg)。opargはopcodeに基づいて参照先を認識します。たとえば、LOAD_NAME opcodeでは、opargはco_namesタプルのインデックスを指します。
  • 解決された引数(括弧内)

インデックス6を見ると、LOAD_CONST opcodeはco_constsタプルから読み込むオブジェクトを指すopargを取得しています。ここでは型宣言Aを指します。すべてのコード・オブジェクトの逆コンパイルを反復処理することにより、モジュールのバイトコード全体を取得できます。

バイトコードの最初の部分(インデックス0~16)はAの型宣言に関連し、残りの部分はAをインスタンス化し、出力するコードを示しています。このコードにも、バイトコードや型の変更などを予定していない場合には適さないコンストラクタがあります。

興味深いバイトコードのコンストラクタ

命令コードは総体的に簡潔ですが、次の処理を経ているために奇妙に見えるものもいくつかあります。

  • コンパイラの最適化
  • インタープリタの最適化(これにより余分な命令コードが生じる)
シーケンスを用いた変数への代入

最初のカテゴリでは、ソースが変数のシーケンスを代入するとどうなるかを見ていきます。

(1) a, b = 1, '2'
(2) a, b = 1, e
(3) a, b, c = 1, 2, e
(4) a, b, c, d = 1, 2, 3, e

上記の4つのステートメントは全く異なるバイトコードを生成します。

最初のステートメントは、右辺(RHS)に代入された値が定数のみなので最も単純なケースです。この場合、CPythonはUNPACK_SEQUENCEを用いてタプル(1, '2')を作成し、2つの要素をスタックに設定して、変数abのそれぞれについてSTORE_FASTを作成することができます。

0 LOAD_CONST               5 ((1, '2'))
3 UNPACK_SEQUENCE          2
6 STORE_FAST               0 (a)
9 STORE_FAST               1 (b)

ところが、2番めのステートメントでは、右辺に変数があるため、ジェネリック型のケースが呼び出され、そこで式が取り出されます。(ここではLOAD_GLOBALを使用した単純な式)。コンパイラではスタック上の値(インデックス18)から新しいタプルを作成する必要はなく、UNPACK_SEQUENCEを使用します。スタックの一番上の2つの要素を入れ替えるROT_TWOを呼び出すにはこれで十分です(19と22を入れ替えても十分だったかもしれません)。

12 LOAD_CONST               1 (1)
15 LOAD_GLOBAL              0 (e)
18 ROT_TWO
19 STORE_FAST               0 (a)
22 STORE_FAST               1 (b)

3番目のケースは実に不思議です。スタックに式を入れるメカニズムは前のケースと同じですが、この場合は一番上の3つの要素を入れ替えた後、さらに一番上の2つの要素を入れ替えます。

25 LOAD_CONST               1 (1)
28 LOAD_CONST               3 (2)
31 LOAD_GLOBAL              0 (e)
34 ROT_THREE
35 ROT_TWO
36 STORE_FAST               0 (a)
39 STORE_FAST               1 (b)
42 STORE_FAST               2 (c)

4番目のケースはジェネリック型のケースを表し、ROT_*を使った処理はこれ以上できないらしく、タプルを作成し、UNPACK_SEQUENCEの呼び出しでタプルをスタックに追加しています。

45 LOAD_CONST               1 (1)
48 LOAD_CONST               3 (2)
51 LOAD_CONST               4 (3)
54 LOAD_GLOBAL              0 (e)
57 BUILD_TUPLE              4
60 UNPACK_SEQUENCE          4
63 STORE_FAST               0 (a)
66 STORE_FAST               1 (b)
69 STORE_FAST               2 (c)
72 STORE_FAST               3 (d)
callコンストラクタ

最後にご紹介する興味深い例は、callコンストラクタと呼び出しを作成する4種類の命令コードに関するものです。この命令コードの数は、インタープリタのコードを最適化するために想定しました。なぜなら、Javaのようにinvokedynamicinvokeinterfaceinvokespecialinvokestaticinvokevirtualのいずれか1つがあれば意味を成すというわけにはいかないからです。

Javaのinvokeinterfaceinvokespecialinvokevirtualは言語の静的型付けから派生しています(またinvokespecialはコンストラクタとスーパークラスAFAIKの呼び出しのみに使用されます)。invokestaticは自己記述型(スタックにレシーバを追加する必要がない型)ですが 、Pythonにはそのような概念がありません(インタープリタで処理し、デコレータを使用しない)。つまり、Pythonで呼び出すとしたら、必ずinvokedynamicで翻訳されることになります。

ここではPythonのさまざまなCALL_*命令コードは取り上げていません。なぜなら型付けや静的メソッドがあったり、コンストラクタ用の特殊なアクセスが必要なためです。これらはすべてPythonのメソッド呼び出しの指定方法を対象にしています。文法は次のとおりです。

  Call(expr func, expr* args, keyword* keywords,
       expr? starargs, expr? kwargs)

calls構造体のコードは次のように記述できます。

func(arg1, arg2, keyword=SOME_VALUE, *unpack_list, **unpack_dict)

キーワード引数はパラメータを位置だけではなく、名前指定で渡すことができます。*はイテラブルからのすべての要素を引数(タプルではなくインライン)として指定し、**はキーワードと値の辞書を想定します。

次の例ではcall siteコンストラクタの可能なすべての機能を実際に使用しています。

  • 変数の引数リストを渡す(_VAR):CALL_FUNCTION_VARCALL_FUNCTION_VAR_KW
  • キーワードベースの辞書を渡す(_KW):CALL_FUNCTION_KWCALL_FUNCTION_VAR_KW

バイトコードは次のようになります。

 0 LOAD_NAME                0 (func)
 3 LOAD_NAME                1 (arg1)
 6 LOAD_NAME                2 (arg2)
 9 LOAD_CONST               0 ('keyword')
12 LOAD_NAME                3 (SOME_VALUE)
15 LOAD_NAME                4 (unpack_list)
18 LOAD_NAME                5 (unpack_dict)
21 CALL_FUNCTION_VAR_KW   258

通常CALL_FUNCTIONはopargとして関数の引数の数を受けとりますが、ここではその他の情報もエンコーディングされています。1バイト目(0xffマスク)は引数の数、2バイト目(value >> 8) & 0xff)は渡されるキーワード引数の数を指定します。スタックからポップする要素の数を計算するには、次のようにして値を取得する必要があります。

na = arg & 0xff         # num args
nk = (arg >> 8) & 0xff  # num keywords
n_to_pop = na + 2 * nk + CALL_EXTRA_ARG_OFFSET[op]

CALL_EXTRA_ARG_OFFSETにはcall命令コード個別のオフセット(CALL_FUNCTION_VAR_KWの場合は2)が格納されます。この例では関数名にアクセスする前にポップする要素の数として6が返されています。

その他のCALL_*キーワードに関しては、コードでリスト渡しの引数と辞書渡しの引数のどちらを使用しているかによって決まります。要は組み合わせの問題です。

簡素なCFGを作成する

コードの実際の動作を理解するには、制御フローグラフ(CFG)を作成すると、どのような場合に命令コードのどの無条件シーケンス(基本ブロック)が実行されるかを追跡することができます。

バイトコードは簡素な言語ですが、信頼性の高いCFGを作成するにはこのブログ投稿では書ききれなかった詳細情報が必要なので、CFGの作成を実装する場合にはequipを参照してください。

次に、制御フローがifステートメントのみに依存するループ/例外のフリーコードを中心に説明します。

ジャンプ先アドレスの受け渡しには、次のような短い命令コード(ループなし/例外)を使用します。

  • JUMP_FORWARD:バイトコードの相対ジャンプ先。スキップするバイトサイズを受けとります。
  • JUMP_IF_FALSE_OR_POPJUMP_IF_TRUE_OR_POPJUMP_ABSOLUTEPOP_JUMP_IF_FALSEPOP_JUMP_IF_TRUE:いずれもバイトコードの絶対インデックスを受けとります。

関数のCFGを作成するということは、基本ブロック(例外が発生しない限り無条件に実行される一連の命令コード)を作成し、それを条件分岐を含むグラフ内で結合することを意味します。この例で使用している分岐は、TrueFalseUnconditionalのみです。

次のコード例を考えてみましょう(実際には決して使わないでください)。

def factorial(n):
  if n <= 1:
    return 1
  elif n == 2:
    return 2
  return n * factorial(n - 1)

前述したように、factorialメソッドのコード・オブジェクトを取得します。

module_co = compile(python_source, '<string>', 'exec')
meth_co = module_co.co_consts[0]

これを逆アセンブルすると次のようになります(筆者の注釈は除外してください)。

3           0 LOAD_FAST                0 (n)
            3 LOAD_CONST               1 (1)
            6 COMPARE_OP               1 (<=)
            9 POP_JUMP_IF_FALSE       16              <<< control flow

4          12 LOAD_CONST               1 (1)
           15 RETURN_VALUE                            <<< control flow

5     >>   16 LOAD_FAST                0 (n)
           19 LOAD_CONST               2 (2)
           22 COMPARE_OP               2 (==)
           25 POP_JUMP_IF_FALSE       32              <<< control flow

6          28 LOAD_CONST               2 (2)
           31 RETURN_VALUE                            <<< control flow

7     >>   32 LOAD_FAST                0 (n)
           35 LOAD_GLOBAL              0 (factorial)
           38 LOAD_FAST                0 (n)
           41 LOAD_CONST               1 (1)
           44 BINARY_SUBTRACT
           45 CALL_FUNCTION            1
           48 BINARY_MULTIPLY
           49 RETURN_VALUE                            <<< control flow

このバイトコードにはCFGの構造を変更する5つの命令があります(制約を追加するか、すぐに終了できるようにしています)。

  • POP_JUMP_IF_FALSE:絶対インデックス16と32にジャンプします。
  • RETURN_VALUE:スタックから要素を1つポップして返します。

検索対象は制御フローを変更するこれらの命令だけなので、基本ブロックの抽出は容易になります。この例ではフォールスルーを禁止しているジャンプはなく、JUMP_FORWARDまたはJUMP_ABSOLUTEがその処理を実行します。

そのような構造を抽出するコードの例を次に示します。

import opcode
RETURN_VALUE = 83
JUMP_FORWARD, JUMP_ABSOLUTE = 110, 113
FALSE_BRANCH_JUMPS = (111, 114) # JUMP_IF_FALSE_OR_POP, POP_JUMP_IF_FALSE

def find_blocks(meth_co):
  blocks = {}
  code = meth_co.co_code
  finger_start_block = 0
  i, length = 0, len(code)
  while i < length:
    op = ord(code[i])
    i += 1
    if op == RETURN_VALUE: # We force finishing the block after the return,
                           # dead code might still exist after though...
      blocks[finger_start_block] = {
        'length': i - finger_start_block - 1,
        'exit': True
      }
      finger_start_block = i
    elif op >= opcode.HAVE_ARGUMENT:
      oparg = ord(code[i]) + (ord(code[i+1]) << 8)
      i += 2
      if op in opcode.hasjabs: # Absolute jump to oparg
        blocks[finger_start_block] = {
          'length': i - finger_start_block
        }
        if op == JUMP_ABSOLUTE: # Only uncond absolute jump
          blocks[finger_start_block]['conditions'] = {
            'uncond': oparg
          }
        else:
          false_index, true_index = (oparg, i) if op in FALSE_BRANCH_JUMPS else (i, oparg)
          blocks[finger_start_block]['conditions'] = {
            'true': true_index,
            'false': false_index
          }
        finger_start_block = i
      elif op in opcode.hasjrel:
        # Essentially do the same...
        pass

  return blocks

これで次の基本ブロックが得られます。

Block  0: {'length': 12, 'conditions': {'false': 16, 'true': 12}}
Block 12: {'length': 3, 'exit': True}
Block 16: {'length': 12, 'conditions': {'false': 32, 'true': 28}}
Block 28: {'length': 3, 'exit': True}
Block 32: {'length': 17, 'exit': True}

現在のブロックの構造は次のようになります。

Basic blocks
  start_block_index :=
     length     := size of instructions
     condition  := true | false | uncond -> target_index
     exit*      := true

制御フローグラフ(ブロックのエントリーと暗黙的returnを差し引いたもの)が得られ、それをたとえばドットに変換して表示することもできます。

def to_dot(blocks):
  cache = {}

  def get_node_id(idx, buf):
    if idx not in cache:
      cache[idx] = 'node_%d' % idx
      buf.append('%s [label="Block Index %d"];' % (cache[idx], idx))
    return cache[idx]

  buffer = ['digraph CFG {']
  buffer.append('entry [label="CFG Entry"]; ')
  buffer.append('exit  [label="CFG Implicit Return"]; ')

  for block_idx in blocks:
    node_id = get_node_id(block_idx, buffer)
    if block_idx == 0:
      buffer.append('entry -> %s;' % node_id)
    if 'conditions' in blocks[block_idx]:
      for cond_kind in blocks[block_idx]['conditions']:
        target_id = get_node_id(blocks[block_idx]['conditions'][cond_kind], buffer)
        buffer.append('%s -> %s [label="%s"];' % (node_id, target_id, cond_kind))
    if 'exit' in blocks[block_idx]:
      buffer.append('%s -> exit;' % node_id)

  buffer.append('}')
  return '\n'.join(buffer)

こんな面倒が必要か?

Pythonのバイトコードにアクセスすることはきわめて稀ですが、筆者は過去に何度かその機会がありました。この情報がPythonのリバース・エンジニアリング・プロジェクトに着手しようとしている方のお役に立てば幸いです。

このところ筆者はPythonのコード、特にバイトコードを埋め込むことができるかを調査していました。Pythonにはそれを実現する機能がないからです(しかもソースコードを埋め込むと多くの場合にデコレータなどを使用した非効率な挿入コードが残ります)。そこでequipが誕生しました。