動的に生成される文書の XHTML 妥当性検査
Validating Dynamically Generated XHTML Documents
乙井 信男 †

南出 靖彦 †

Nobuo OTOI, Yasuhiko MINAMIDE†筑波大学システム情報工学研究科

Graduate School of Systems and Information Engineering, University of Tsukuba{otoi,minamide}@score.cs.tsukuba.ac.jp
これまで HTML の妥当性検査は静的な Web ページに対し適用され、動的に Web ページが生成される場合検査する手法はなかった．そこで本論文ではサーバーサイドプログラムの出力をプログラム解析の手法を用いて文脈自由文法に近似し、動的な Web ページが XHTML の仕様を満たすか検査する手法を提案、実装する．仕様を表すオートマトンを単純に構成すると状態数が指数関数的に増えてしまい、実用に耐えられないことから、DTD の局所性を用いた検査を実装する.

1

する文書の XHTML 妥当性を検査する.

はじめに今回提案する検査では、文字列解析器の出力する

動的な Web ページは静的な Web ページよりもク

文脈自由言語が XHTML の妥当性を満たすか検査すライアントの要求に柔軟に対応できることから、多る. XHTML に適合する文字列の集合は文脈自由文

くの Web サイトで用いられている. 動的な Web ペー法を用いて表す事ができるので、文脈自由言語同士ジはサーバーサイドで生成され、このとき用いられの包含関係が決定できれば妥当性を検査できる. しるプログラムはサーバーサイドプログラムと呼ばれる. 動的な Web ページは柔軟な表現ができる一方で、適切な処理をしないと Web ページに脆弱性などの問かしこの包含関係は決定不能問題であり、単純に検査できない. そこで本研究では対象とする文章の深さを制限する事で検査を可能にする.

題が含まれる可能性がある.
こうした背景から、サーバーサイドプログラムを2解析し、その性質を検証する研究が行われている [2].

文字列解析器我々が代表的なサーバーサイド言語である PHP を対

近年、プログラムの生成する文字列の集合を近似象にしたプログラムの文字列解析器を開発しているする研究が行われている [1][5]. 我々もまた、PHP プ[4] . この解析器は、PHP プログラムが出力する可能性のある文字列の集合を文脈自由文法を用いて近似する. この解析によって得られた文脈自由文法をもとに、動的に生成される Web ページを検査することができる. 例えば、クライアントのどのような要求に対しても PHP プログラムが必ず仕様を満たす文字列を出力するかチェックすることで安全性を検査することができる.

ログラムを対象に、文字列の集合を文脈自由言語に近似して出力する文字列解析器を開発している. この解析器には PHP プログラムと入力に関する仕様を与える必要がある. 解析器の動作を示すために、以下に PHP プログラムの例を示す.

<?php
for ($i = 0; $i < $n; $i++)$x = "<table><tr><th>".$x.
"</th></tr></table>";一方、サーバーサイドプログラムの抱える問題とecho $x;して、妥当性の問題がある. 静的な Web ページが?>HTML や XHTML の規格に対する妥当性を検査するツールは数多く利用されているが、動的に生成す PHP のプログラムは<?で始まり、?>で終わる. 変る文書では、Web ページを静的に決定できないため 数名は$から始め、この例では$x, $i, $n が変数でに妥当性の検査をすることができなかった. 本研究 ある.
このプログラムに文字列解析器を適用するためにでは我々が開発している文字列解析器を用いることで PHP プログラムを解析し、そのプログラムが生成 は、変数の初期値を仕様として与える必要がある. 仕1

日本ソフトウェア科学会第 22 回大会（2005 年度）論文集

2

様には以下のように正則表現か変数の型を書く事がす最小の文書は htableihtrihthih/thih/trih/tablei とできる.

htableihtrihtdih/tdih/trih/tablei である.

$x: /abc|xyz/$n: int
ここでは、$x の値は abc または xyz、$n は int 型であることを表している. 解析器は、これらの情報を基にプログラムの出力を文脈自由文法を用いて近似する. この例では、以下のような生成規則が得られる.
XXX→ abc→ xyz→ htableihtrihthiXh/thih/trih/tablei

このプログラムは、テーブルタグが n 回ネストする文字列を出力する. 一方、上の文脈自由法は、下の文字列の集合と等価であり、正しい近似になっている.
{(htableihtrihthi)n abc(h/tableih/trih/thi)n | n ≥ 0}∪{(htableihtrihthi)n xyz(h/tableih/trih/thi)n | n ≥ 0}

上のように得られた文脈自由文法を用いてプログラムの性質を検査することができる.

4

XHTML 妥当性検査
本研究は、PHP プログラムの出力する Web ページが必ず XHTML の仕様を満たすか検査する. この検査は PHP プログラムの出力する文字列を表す文脈自由文法 G に対し、L(G) ⊂ L(XHTML) で表すことができるが、この関係を直接調べることはできな
い. ここでの問題は、XHTML の仕様は本質的に文脈自由文法であり、文脈自由文法同士の包含関係は決定不能問題であることである.
この問題を解決するために、PHP プログラムによって生成される XHTML 文書のタグのネストの深さが有限の場合に関して、検査を行うことにする. 多くのサーバーサイドプログラムは、テーブル構造を持つ Web ページを生成するので、生成する Web ペー
ジの深さは、有限になると考えている.
深さを制限することで、妥当な XHTML 文書の集合は正則言語で表すことができる. 深さ i 以下の妥
当な XHTML 文書の集合を XHTMLi とすると以下

3

XHTML と DTD本研究で妥当性を検査する XHTML とは、HTMLを XML の文法に適合するよう定義し直したマークアップ言語である. HTML の文法は複雑であるのに対し、XHTML の文法はシンプルなので妥当性の検査が簡単になる. XHTML の文法は、XML 文書の構造を定義する DTD(Document Type Defini-の検査を行うことになる.

L(G) ⊂ L(XHTML)i
この包含関係の検査は、右辺が正則言語の場合は検査可能であり、本研究では、Melski と Reps によるアルゴリズム [3] を用いた.

具体的には、深さが i 以下の XHTML 文書を表すtion) を用いて与えられている. 以下に、XHTML のオートマトン F Ai を、XHTML の DTD から生成しDTD の一部を単純化したものを示す. DTD では、た. オートマトン F Ai は、図 1 のように、まず、各<!ELEMENT table (tr)>
タグと深さにに対して、対応する正則言語を求める<!ELEMENT tr (th|td)>
ことによって構成した.
<!ELEMENT th (table)?>
しかし、XHTML の DTD に対して、直接に上の<!ELEMENT td (table)?>オートマトンを構成すると、その DTD が？？？大きいのでの、巨大なオートマトンができる. 一方、解析対
図 2: DTD の例

象の PHP プログラムの文法 L(G) が HTML 上の全てのタグを出力する文法とは限らない. そこで、DTDELEMENT で要素宣言を行う. 図 2 の 1 行目では の文法から検査に不必要なタグに関する文法を取り
要素 table が内容モデル tr をとっている. これは、 除いた DTD’ を構成し、DTD’ が表す言語 XHTML’htableihtri...h/trih/tablei のように、タグ table の中 に対して L(G) ⊂ XHTML’ i を検査する.
また、実際に検査を行う場合には、前もって、生にタグ tr が現れることを表す. 同様に 2 行目では要素tr の内容モデルが (th|td) となっており、これはタグ 成される文書の深さの最大値はわからない. そこで、
th, td のどちらか 1 つをを内部に持たなくてはならな 妥当性の検査は検査する最大の深さを定め、深さ 1いことを意味する. この DTD に対して妥当性を満た から順に検査を行った.

日本ソフトウェア科学会第 22 回大会（2005 年度）論文集

table0 → φ
tr0 → φth0 → φtd0 → φtable1 → htableitr0 h/tablei
tr1 → htri(th0 +td0 )h/tri
th1 → hthi(²+table0 )h/thi
td1 → htdi(²+table0 )h/tdi

====

φ
φ
hthih/thihtdih/tdi

table2 → htableitr1 h/tablei
tr2 → htri(th1 +td1 )h/tri
th2 → hthi(²+table1 )h/thi
td2 → htdi(²+table1 )h/tdi
table3 → htableitr2 h/tablei=====

tr3 → htri(th2 +td2 )h/tri
th3 → hthi(²+table2 )h/thi
td3 → htdi(²+table2 )h/tdi

=
=
=

3

φ
htri(hthih/thi + htdih/tdi)h/tri
hthih/thihtdih/tdi
htableihtri(hthih/thi+htdih/tdi)h/trih/tablei
htri(hthih/thi + htdih/tdi)h/tri
hthih/thihthih/thi

図 1: タグから正則言語へのテーブル
この検査を実装し、SourceForge から配布されているオープンソースプログラム WebCalendar に対して実験を行った. 実験はこのプログラムのメインページ

グの孫として、ある別のタグが必要であるというよ
うな制約は記述できない.
そこで、各深さ k ごとに、深さ k と k +1 について、を生成する month.php を対象にし、DTD には DTD 親子関係の制約を検査する. 具体的には、XHTMLiXHTML 1.0 Transitional を用いた. 予備的な実験に に対して、上の制約のみを検査するオートマトン
より、このプログラムは深さ 7 の文書を生成するこ F A0i,k (1 ≤ k < i) を作成し、各 k について包含関とがわかっている. 結果はタグの深さ 7 で検査中、マ 係を確かめる. これにより、検査時の状態数を減らシンのメモリーが不足して検査は失敗した. 以下は、 しながら、妥当性の検査を行うことができる.
この実験で得られたタグの深さとオートマトンの状
L(G) ⊂ F Ai ⇔態数の関係である.
L(G) ⊂ F A0 ∧ · · · ∧ L(G) ⊂ F A0i,1

タグの深さ
状態数

327641475582836363697143237

ここから、オートマトンの状態数がタグの深さに対し指数関数的に増えていることがわかる. 一方、検i,i−1

オートマトン F A0i,k は R(x), f (DT D) および g(C)を用いて以下のように定義する. ただし en , Cn はそれぞれ DTD における要素と内容モデルを表し、<!ELEMENT en Cn >を意味する.

査で用いている文脈自由言語と正則言語の共通部分の計算がオートマトンの状態数の 3 乗のアルゴリズムであることから、タグのネストが深くなることで計算量が膨大になったと考えられる.
また、この実験の中で、DTD の 1 回以上繰り返しを表す表現 X+に対応するプログラムに関して、文字列解析器が不十分な精度の文脈自由文法を生成することが多いことがわかった. 厳密な妥当性の検査ではなくなるが、本研究では、DTD の 1 回以上繰り返しを表す表現 X + を X ∗ として検査を行った.

5

DTD の局所性を用いた検査の改良
前節の実験によってオートマトンの状態数がタグの深さに対し指数関数的に増えてしまうことが分かった. そこで状態数の増加を DTD の局所性を用いて抑制する手法を考える. 状態数が爆発した原因は、DTD によって表される制約を一つのオートマトンで表すと、タグのネストの深さに対し指数関数的にその状態数が増加してしまうためだと考えられる. 一方、DTD には、ある要素とその子要素の関係しか記述できないという局所性がある. すなわち、あるタ

R(x) = (h.∗i...(h.∗ih/.∗i)∗ ...h/.∗i)∗| {z }x個
f (DT D) = he1 ig(C1 )h/e1 i + he2 ig(C2 )h/e2 i + · · ·haiR(i − k − 1)h/ai C = ag(D) + g(E)C =D+Eg(D) + ²C = D?
g(C) =
g(D)g(E)C = DE
(g(D))∗
C = D∗
(g(D))∗
C = D+F A0i,k = (h.∗i...(h.∗i f (DT D)h/.∗i)∗ ...h/.∗i)∗| {z }
k−1個
このアルゴリズムで得られる正則言語は、ある深さ k と k + 1 以外のタグは常に左右のバランスしかチェックしないため、深さに対して線形の状態数をもつオートマトンで表すことができる. 例えば、このアルゴリズムを図 2 の DTD に対して適用し、F A03,1日本ソフトウェア科学会第 22 回大会（2005 年度）論文集

㪈㪍㪇㪇㪇㪇4㪍㪇㪇㪇㪈㪋㪇㪇㪇㪇㪌㪇㪇㪇㪈㪉㪇㪇㪇㪇㪋㪇㪇㪇

FA iFA'i,k㪏㪇㪇㪇㪇㪍㪇㪇㪇㪇⁁ᘒᢙ⁁ᘒᢙ㪈㪇㪇㪇㪇㪇㪊㪇㪇㪇㪉㪇㪇㪇㪋㪇㪇㪇㪇㪈㪇㪇㪇㪉㪇㪇㪇㪇㪇㪈㪉㪊㪋㪌࠲ࠣߩࡀࠬ࠻ߩᷓߐ㪍㪎

図 3: WebCalendar 検査時の状態数比較を求めると、以下の正則表現が得られる.

㪇㪈㪉㪊㪋㪌㪍㪎㪏㪐࠲ࠣߩࡀࠬ࠻ߩᷓߐ㪈㪇㪈㪈㪈㪉㪈㪊㪈㪋

図 4: phpScheduleIt 検査時の状態数
文書は妥当性を満たすことがわかった.

htableihtri(h.∗ih/.∗i)∗ h/trih/tablei+htri(hthi(h.∗ih/.∗i)∗ h/thi + htdi(h.∗ih/.∗i)∗ h/tdi)h/tri 6.2 解析精度とバグの検出+hthi(htablei(h.∗ih/.∗i)∗ h/tablei + ²)h/thi
前節で述べた実験において、文字列解析を行い、十+htdi(htablei(h.∗ih/.∗i)∗ h/tablei + ²)h/tdi

分な解析精度で妥当性の検査を行うためには、プロ6

実験

グラムを書き換える必要がある箇所がいくつかあっ

6.1

状態数の変化

まず、以下のように if 文を用いてある条件が成り立前節の検査アルゴリズムを用いて、SourceForge から配布されているオープンソースプログラム WebCal-endar と phpScheduleIt に対して実験を行った.

た. ここでは、WebCalendar の検査について述べる.
つときにif ( $pri == 3 ) echo "<strong>";...
if ( $pri == 3 ) echo "</strong>\n";

WebCalendar に関して、F Ai の状態数と、F A0i,kの状態数をグラフで表したものが図 3 である. ただし F A0i,k は同じ深さのオートマトンの中で最も状態 対応する開始タグと終了タグを出力するものである.
数が大きくなる値 k を選んだ場合である. F Ai では 文字列解析器は、if 文の条件部分を無視するため、妥深さとともに指数関数的に状態数が増えるのに対し、 当性の検査に失敗する. そこで、このプログラムは、
F A0i,k ではほぼ線形にとどめることができた.
以下のように書き換え検査を行った.
この実験の中で、文字列解析器の近似が粗すぎるために検査が失敗する場合、また、WebCalendar に対応しない開始タグと終了タグを出力するバグがあるため検査が失敗する場合があった. 上の実験は、より正確に近似できるプログラムに書き換え、また発見したバグは修正し行った. これらに関しては、次節で述べる.
さらに、よりタグのネストが深い例として、PHP で書かれたスケジュール管理プログラム phpScheduleIt

if ( $pri == 3 ) {echo "<strong>";foo(...)
echo "</strong>\n";} elsefoo(...);
ここで、関数 foo は、上のプログラムの... 部分を実行する関数として定義した.の検査を行った. 前準備として、関数 eval などのプ

また、配列の操作に関して十分な精度が得られなログラム解析をするうえでサポートするのに困難ない部分も 2 箇所見つった. それらも、同じ動作を行関数を同等なプログラムに置き換えた. この検査結果

うがより正確に近似できるプログラムに書き換え実を図 4 に示す. タグのネストがより深いこの例におい験を行った.ても状態数の増加は線形であることが確認できた. さ

これらの書き換えを行っても、WebCalendar の検らに検査によりこのプログラムの生成する XHTML査は失敗した. そのため、検査によって得られた反例

日本ソフトウェア科学会第 22 回大会（2005 年度）論文集とプログラムを比較し、プログラムに対応しない開始タグと終了タグを出力するバグがないか調べ、そのようなバグが 2 箇所あることがわかった. このバグは、WebCalendar の開発者に報告した.

7

まとめPHP の文字列解析器によって得られる文脈自由文法を用いて XHTML の妥当性を検査する手法を提案し、実装した. さらに、オープンソースの PHP プログラムに対して実験を行った結果、DTD から生成されるオートマトンの状態数が指数関数的に増えることが問題となった. それに対してオートマトンをタ
グの深さを 2 ステップずつ検査するように分割することで状態数の爆発を防ぐ改良手法を提案した. これによってタグのネストが深いプログラムに対しても検査することができるようになり、妥当性を満たさないプログラムを見つけることができた.
提案した検査手法は、いくつかの意味で厳密でない. 4 節で述べたように文字列解析器が言語中の 1 回以上繰り返しを 0 回以上繰り返しとして近似してしまうため、DTD 中の内容モデルも合わせて X + をX ∗ とみなして検査を行った. この点で妥当性の検査精度が低くなってしまった. 今後は X + を X + として検査するには、どれくらい PHP プログラムを書き換える必要があるか調べたい. また、DTD に記述される情報は要素の親子関係だけではない. 要素の属性に関する検査を行いたい.
参考文献[1] Aske Simon Christensen, Anders Møller, andMichael I. Schwartzbach. Precise analysis of stringexpressions. In Proc. 10th International Static Analysis Symposium, SAS ’03, Vol. 2694 of LNCS, pp.
1–18. Springer-Verlag, June 2003.
[2] Yao-Wen Huang, Fang Yu, Christian Hang, ChungHung Tsai, Der-Tsai Lee, and Sy-Yen Kuo. Securing
web application code by static analysis and runtime
protection. In Proceedings of the 13th international
conference on World Wide Web, pp. 40–52, USA,2004.
[3] David Melski and Thomas Reps. Interconvertibilityof a class of set constraints and context-free language reachability. Theoretical Computer Science,Vol. 248, No. 1–2, pp. 29–98, 2000.
[4] Yasuhiko Minamide. Static approximation of dynamically generated Web pages. In Proc. 14th International World Wide Web Conference, pp. 432–441,May 2005.

5[5] N. Tabuchi, E. Sumii, and A. Yonezawa. Regularexpression types for strings in a text processing language. In Proceedings of Workshop on Types in Programming (TIP), pp. 1–18, 2002.