Generating Control Flow Graph using C Intermediate Language (CIL)

C プログラムから Control Flow Graph（CFG）を取り出す必要があり、色々と調べてみた。結果、以下の2つの方法が有望そう。1つはgcc の"-fdump-tree-fixupcfg" オプションを使う方法。もう一つは、Berkley が作っている C Intermediate Language (CIL) を使う方法。gcc はオプションで簡単に出せるのでこっちでいいかなぁ、と考えていたら、同僚からは、gcc はドキュメントがないから、まじめにやるのであれば CILを薦められた。

ただ、このCILが使い方が結構厄介。まず、最初は Windows上でインストールしようとしたのだが、うまくいかず。あれこれ時間かかってできなくて、結局あきらめてLinux上でやるとあっさりインストール成功。これだけで多くの時間を費やしてしまう。どうやら、CILというよりも、CILの実装言語であるOcamlがWindowsはあまりサポートされていない模様。

さて、インストールが成功したので、次は、CILを使って、CFGを出すという作業。

CILは、インストールを澄ますと、コマンドラインからアクセスする方法と、Ocamlのプログラムからアクセスする方法の二つの方法がある。コマンドラインで、CILからCFGを出すには"--domakeCFG" オプションで、以下の通り実行すればよいとのこと。

cilly.asm.exe --domakeCFG sample.c --out sample.o

しかし、出力ファイルを見ると、なんとなくCFGが生成されていないような気がする。私の読み方が悪いのかもしれないが。

というわけで、もう一つの方法である、OcamlコードからCFGの取り出しを試してみることに。ただこれがなかなか骨が折れる作業である。なぜなら、私はOcamlを知らないから。言語設計はともかく、環境も、ocamlfind、ocamloptいろいろありこれらをゼロから学ぶのは骨が折れる。

そんな折、参考になるのがサンプルコード。CILのOcamlコードからの扱いのサンプルコードを探すと以下のページにたどり着く。

Using CIL to analyze libvirt

このサンプルコードをちょっとずつ直して、自分のやりたいSample.cからCFGを生成することに。

まず上記のサイトより、cil-testing-1.1.tar.gz を取得。

実行方法は、make run-ciltest1 を実行すると以下の表示が得られる。

test1.c:11: test1_add has 2 arg(s)
test1.c:22: test1_inc has 1 arg(s)
test1.c:36: test1_print has 1 arg(s)
test1.c:48: test1_last_error has 0 arg(s)
test1.c:56: test1_print_last_error has 0 arg(s)
main.c:10: main has 0 arg(s)

すると、test1.c 内のすべての関数についてのCFGが、.dot 形式で出力されているので、それをGraphbiz等で開けばよい。

さて。

このOcamlプログラムはCFGの出力が、test1.cに固定であったが、任意のCプログラムに対してCFGを取得することを試みる。ここでは、以下のSample.cを例にで実演する。

#include <stdio.h>

#include "sample.h"

int someFunction (int a, int b) {
 int result = 0; 
 if (a < b && a != result) { 
 return 0; 
 }
 else {
   int c = a + b; 
   int i = 0; 
 while (i < c) { 
   result = (result + a) / b;
   i++;
 }
}
return result; 
}

この手持ちのSample.cのCFGをCil-testingをもとに作る際、変更・新規作成が必要なファイルは以下の4つ。

• Makefile（変更）
• sample.ml（新規作成）
  • test1.mlをもとに作る。
• sample.h (新規作成)
• main.c

まず、変更対象のMakefileである、cil-testing に同梱されているMakefaileに以下の記述を追加。

sample: sample.cmx
	ocamlfind ocamlopt $(OCAMLOPTFLAGS) $(OCAMLOPTINCS) $(OCAMLOPTPACKAGES) $(OCAMLOPTLIBS) $^ -o $@

run-sample: sample sample.i main.i
	./sample

また各所test1.iが現れる個所に、sample.iを追加。つまり、全体で以下のようなMakefileとなる。

# $Id: Makefile,v 1.4 2007/07/07 13:41:23 rjones Exp $

PACKAGE := cil-testing
VERSION := 1.1

CC	:= gcc
CFLAGS	:= -Wall -Werror

LIBVIRTDIR := /home/rjones/d/libvirt-cil

OCAMLCFLAGS := 
OCAMLCPACKAGES := -package unix,str,cil

OCAMLOPTFLAGS := $(OCAMLCFLAGS)
OCAMLOPTINCS := $(OCAMLCINCS)
OCAMLOPTPACKAGES := $(OCAMLCPACKAGES)
OCAMLOPTLIBS := -linkpkg

all:	test cilprint ciltest1 cilimportvirt sample

test:	main.o test1.o sample.o
	$(CC) $(CFLAGS) $^ -o $@

cilprint: cilprint.cmx
	ocamlfind ocamlopt $(OCAMLOPTFLAGS) $(OCAMLOPTINCS) $(OCAMLOPTPACKAGES) $(OCAMLOPTLIBS) $^ -o $@

run-cilprint: cilprint test1.i main.i
	@./cilprint

ciltest1: ciltest1.cmx
	ocamlfind ocamlopt $(OCAMLOPTFLAGS) $(OCAMLOPTINCS) $(OCAMLOPTPACKAGES) $(OCAMLOPTLIBS) $^ -o $@

run-ciltest1: ciltest1 test1.i main.i
	./ciltest1

###################################################
## 追加部分　ここから ###

sample3: sample3.cmx
	ocamlfind ocamlopt $(OCAMLOPTFLAGS) $(OCAMLOPTINCS) $(OCAMLOPTPACKAGES) $(OCAMLOPTLIBS) $^ -o $@

run-sample3: sample3 sample3.i main.i
	./sample3

## 追加部分　ここまで ###
###################################################

cilimportvirt: cilimportvirt.cmx
	ocamlfind ocamlopt $(OCAMLOPTFLAGS) $(OCAMLOPTINCS) $(OCAMLOPTPACKAGES) $(OCAMLOPTLIBS) $^ -o $@

run-cilimportvirt: build-libvirt libvirt-files libvirt-syms cilimportvirt
	./cilimportvirt

build-libvirt:
	if [ ! -f $(LIBVIRTDIR)/Makefile ]; then \
	  cd $(LIBVIRTDIR) && ./autogen.sh; \
	fi
	if [ ! -f $(LIBVIRTDIR)/tests/virshtest.i ]; then \
	  make -C $(LIBVIRTDIR) CC="gcc -save-temps"; \
	  rm -f libvirt-files; \
	fi

libvirt-files:
	find $(LIBVIRTDIR) -name '*.i' | \
	  egrep '/(qemud|src)/' | \
	  egrep -v 'virsh.i' > $@

libvirt-syms:
	egrep -io '\bvir[a-z0-9]+' \
	  < $(LIBVIRTDIR)/src/libvirt_sym.version > $@

# Run the C files through the C preprocessor.

.c.i:
	$(CPP) $< > $@

# Common rules for building OCaml objects.

.mli.cmi:
	ocamlfind ocamlc $(OCAMLCFLAGS) $(OCAMLCINCS) $(OCAMLCPACKAGES) -c $<
.ml.cmo:
	ocamlfind ocamlc $(OCAMLCFLAGS) $(OCAMLCINCS) $(OCAMLCPACKAGES) -c $<
.ml.cmx:
	ocamlfind ocamlopt $(OCAMLOPTFLAGS) $(OCAMLOPTINCS) $(OCAMLOPTPACKAGES) -c $<

# Clean.

clean:
	rm -f *~ *.bak core *.cmi *.cmo *.cmx *.cma *.cmxa *.o *.so *.a \
	  test cilprint *.i ciltest1 *.dot cilimportvirt

# Distribution.

dist:
	$(MAKE) check-manifest
	rm -rf $(PACKAGE)-$(VERSION)
	mkdir $(PACKAGE)-$(VERSION)
	tar -cf - -T MANIFEST | tar -C $(PACKAGE)-$(VERSION) -xf -
	tar zcf $(PACKAGE)-$(VERSION).tar.gz $(PACKAGE)-$(VERSION)
	rm -rf $(PACKAGE)-$(VERSION)
	ls -l $(PACKAGE)-$(VERSION).tar.gz

check-manifest:
	@for d in `find -type d -name CVS | grep -v '^\./debian/'`; \
	do \
	b=`dirname $$d`/; \
	awk -F/ '$$1 != "D" {print $$2}' $$d/Entries | \
	sed -e "s|^|$$b|" -e "s|^\./||"; \
	done | sort > .check-manifest; \
	sort MANIFEST > .orig-manifest; \
	diff -u .orig-manifest .check-manifest; rv=$$?; \
	rm -f .orig-manifest .check-manifest; \
	exit $$rv

.SUFFIXES: .c .i .cmo .cmi .cmx .ml .mli

.PHONY:	run-cilprint run-ciltest1 run-cilimportvirt build-libvirt

次に、test1.ml をベースに、以下のsample.ml を作成。（＃変更点は、test1.ml 中の「test1.i」となっているところを、「sample.i」に変更するだけ。）

sample.ml

(* Test CIL loading and printing of files.
 * $Id: ciltest1.ml,v 1.1 2007/07/07 12:03:30 rjones Exp $
 *)

open Printf
open Cil

let files = [ "sample.i"; "main.i" ]

let () =
  (* Load each input file. *)
  let files =
    List.map (
      fun filename ->
	(* Why does parse return a continuation? *)
	let f = Frontc.parse filename in
	f ()
    ) files in

  (* Merge them. *)
  let file = Mergecil.merge files "test" in

  (* Remove unused prototypes and variables. *)
  Rmtmps.removeUnusedTemps file;

  (* Do control-flow-graph analysis. *)
  Cfg.computeFileCFG file;

  (* Go over the internal CIL structure and print some facts. *)
  printf "CIL has loaded the files, merged them and removed unused code.\n\n";

  printf "Merged file has %d globals ...\n\n" (List.length file.globals);
  List.iter (
    function
    | GType _ -> ()			(* typedef *)
    | GCompTag _ -> ()			(* struct/union *)
    | GCompTagDecl _ -> ()		(* forward prototype of struct/union *)
    | GEnumTag _ -> ()			(* enum *)
    | GEnumTagDecl _ -> ()		(* forward prototype of enum *)
    | GVarDecl _ -> ()			(* variable/function prototype *)
    | GVar _ -> ()			(* variable definition *)
    | GFun (fundec, loc) ->		(* function definition *)
	printf "%s:%d: %s has %d arg(s)\n"
	  loc.file loc.line fundec.svar.vname (List.length fundec.sformals);

	(* If it's a library function, print its CFG to a file. *)
	if loc.file <> "main.c" then
	  Cfg.printCfgFilename (fundec.svar.vname ^ ".dot") fundec

    | GAsm _ -> ()			(* global asm statement *)
    | GPragma _ -> ()			(* toplevel #pragma *)
    | GText _ -> ()			(* verbatim text, comments *)
  ) file.globals;

最後に、以下の二つのファイルの作成。

• sample.h (新規作成)
• main.c(新規作成)

これらは両方とも、cil-testing のコードを使うために、書式をそろえるためのもの。以下の通り作際。

sample.h

/* Fake C library for CIL testing.
 * $Id: sample.h,v 1.1 2007/07/07 10:52:16 rjones Exp $
 */

#ifndef __SAMPLE_H__
#define __SAMPLE_H__

extern int someFunction (int a, int b);

#endif /* __SAMPLE_H__ */

main.c

/* Main program for testing CIL.
 * $Id: main.c,v 1.1 2007/07/07 10:52:16 rjones Exp $
 */

#include <stdio.h>
#include <stdlib.h>

#include "sample.h"

int
main ()
{
  int a, b, c;

  a = 1; b = 3;
  c = someFunction (a, b);
  printf("%d\n", c);  

  exit (0);
}

これでファイルの準備は完了。

以下のコマンドを実行すると、sample.c 中の関数「someFunction」のCFGが、「someFunction.dot」として得られる。

> make run-sample

以上。