XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム 早瀬康裕†, 鷲尾 和則‡, 松下 誠†, 井上 克郎† † 大阪大学大学院情報科学研究科 ‡ 大阪大学大学院基礎工学研究科

背景 HTML文書へのスクリプト埋め込み 既存のHTML構文検証ツールはスクリプトの内容を無視 HTML文書の普及 DTD(文書型定義)にタグ付け規則が定義されている HTML文書へのスクリプト埋め込み スクリプトは任意の HTML 文書の断片を出力することが可能 既存のHTML構文検証ツールはスクリプトの内容を無視

スクリプトによる HTML 生成の例 変数が取りうる値を知る必要 既存のシステムでは script 要素を無視するため、 違反を検出できない <span> <script type="JavaScript"> <![CDATA[ var day = new Date(); var message; if(day.getHour() < 12){ message = "good morning"; } else { "<div>good afternoon</div>"; } document.write(message); ]]> </script> </span> 午前のとき <span> good morning </span> 午後のとき <span> <div>good afternoon</div> </span> DTD違反 変数が取りうる値を知る必要 既存のシステムでは script 要素を無視するため、 違反を検出できない

DTD 検証ツール ECMAX スクリプトの出力を考慮した DTD 検証ツールECMAX † 手順 XHTML 1.0 ECMAScript (ECMA-262) にいくつかの制限を加えたもの (関数やオブジェクトに非対応) 手順 XHTML を解析し、スクリプトを抽出 出力文を探し、出力文の引数が取りうる値を計算 2. の結果と、出力文の属する制御構造 (条件文や繰り返し文) から、出力されうる文字列を計算 3. の結果を、静的な部分と合わせて DTD 検証 引数に変数が含まれていた場合には、 変数が取り得る値を知る必要がある † 鷲尾和則, 松下誠, 井上克郎, “JavaScriptを含んだHTML文書に対するデータフロー解析を 用いた構文検証手法の提案”, 信学技報, SS2002-22, pp. 13-18, 2002

フローグラフ ECMAScript プログラムから、フローグラフを作成 頂点: 文または式 有向辺: 制御が移り得ることを示す 1 m=“abc” m=“abc”; if (x) { m=x; } document.writeln(m); 2 x 3 m=x 4 document.writeln(m)

候補集合 変数が特定の文の実行直後に取り得る値を候補、候補全体の集合を候補集合と呼ぶ 候補とは以下のいずれか 定数 “abc”, 123, true, undefined, null 等 不定値 型の分かっているもの String, Numeric, Boolean 型の分からないもの 未計算の式 式には、候補集合を含む場合がある 候補集合は、変数名と頂点番号の組で識別する 　例:頂点 5 を実行した直後の x の値 ⇒ x5

候補集合の計算 対象頂点を起点として、フローグラフの辺を逆向きにたどり、対象変数への代入文を含む頂点を探す 見つかった頂点それぞれに対して 値を調べたい頂点・変数を、対象頂点・対象変数と呼ぶ 対象頂点を起点として、フローグラフの辺を逆向きにたどり、対象変数への代入文を含む頂点を探す 見つかった頂点それぞれに対して 代入文の右辺に変数を含まないなら、右辺の値を候補集合に追加する 代入文の右辺に変数が含まれる場合 その変数の候補集合を計算中でないなら、候補集合を再帰的に計算し、代入した結果を候補集合に追加 変数の候補集合を計算中の場合は、変数を候補集合の記号で置き換えた、未計算の式を候補集合に追加 m=“abc” m=x x document.writeln(m) 1 2 3 4 m=“abc” m=x

候補集合の計算 対象頂点を起点として、フローグラフの辺を逆向きにたどり、対象変数への代入文を含む頂点を探す 見つかった頂点それぞれに対して a=“abc” a=x x document.writeln(m) 1 2 3 4 m=“abc” m=x m=“abc” 値を調べたい頂点・変数を、対象頂点・対象変数と呼ぶ 対象頂点を起点として、フローグラフの辺を逆向きにたどり、対象変数への代入文を含む頂点を探す 見つかった頂点それぞれに対して 代入文の右辺に変数を含まないなら、右辺の値を候補集合に追加する 代入文の右辺に変数が含まれる場合 その変数の候補集合を計算中でないなら、候補集合を再帰的に計算し、代入した結果を候補集合に追加 変数の候補集合を計算中の場合は、変数を候補集合の記号で置き換えた、未計算の式を候補集合に追加 m=x

候補集合を計算中の場合の処理 変数の計算中の場合は、変数を候補集合の記号で置き換えた未計算の式を候補集合に追加 未計算の式を除去 i1 i3 候補集合自身を含まない候補を代入 新たな候補が得られたら、不定値とする i=0 i=i+1 document.writeln(i) 1 2 3 i1 i3 1, 不定数値 i1 i3 1, i3 + 1 i1 i1 i3 1, … i3+1 の i3 に、 １ を代入 ↓ 2

システムの実装と実験 変数値候補計算アルゴリズムを、XHTML 検証システム ECMAX に実装し、 既存のシステムと比較実験を行った 開発および実行環境 J2SDK 1.3.1, JavaCC 2.1 OS: FreeBSD 4.7 CPU: Pentium4 2GHz RAM: 2GB システムの規模 9,000 行 (うち、値候補計算部は 3,000 行) 比較対象 Another HTML-lint ver2.49 データ JavaScript を含むHTML 文書: 232 個 出展: THE JAVASCRIPT SOURCE http://javascript.internet.com

実験結果 ツール ECMAX htmllint DTD XHTML1- Strict Transitional XHTML構文違反 10 スクリプト構文違反 48 -- スクリプト内XHTML構文違反 43 (14) スクリプト内タグを含めた タグ付け違反 18 (14) DTD違反 113 (35) 65 (12) 153 8 違反なし 0 (0) 48 (23) 69 214 合計 232 (63) 232 ()内は、スクリプトの出力に不定値が含まれていた数

実験結果 htmllint は、スクリプトの中身を考慮しないため、違反なしが多くなっている ツール ECMAX htmllint DTD XHTML1- Strict Transitional XHTML構文違反 10 スクリプト構文違反 48 -- スクリプト内XHTML構文違反 43 (14) スクリプト内タグを含めた タグ付け違反 18 (14) DTD違反 113 (35) 65 (12) 153 8 違反なし 0 (0) 48 (23) 69 214 合計 232 (63) 232 htmllint は、スクリプトの中身を考慮しないため、違反なしが多くなっている ECMAX では、スクリプト内での違反も発見できた ()内は、スクリプトの出力に不定値が含まれていた数

実験結果 出力に不定値が含まれた場合、その中にはタグは無いと仮定している ⇒ 検証結果は確実ではない htmllint ECMAX ツール 48 (23) 65 (12) XHTML1- Transitional 232 (63) 0 (0) 113 (35) 18 (14) 43 (14) 48 10 Strict DTD 232 合計 214 69 違反なし -- スクリプト内タグを含めた タグ付け違反 スクリプト構文違反 8 153 DTD違反 スクリプト内XHTML構文違反 XHTML構文違反 ()内は、スクリプトの出力に不定値が含まれていた数 出力に不定値が含まれた場合、その中にはタグは無いと仮定している 　　⇒　検証結果は確実ではない

実験結果の考察 スクリプトを考慮することで、既存のシステムが見逃していた違反を発見できた 約1/3のデータで、出力に不定値が含まれていた 正しい XHTML 文書作成を補助できる 約1/3のデータで、出力に不定値が含まれていた 不定値を含む検証は、確実ではない 不定値を減らすため、計算精度の向上が必要

まとめと今後の課題 まとめ 今後の課題 ECMAScript プログラムで、変数が取りうる値を計算する手法について説明 XHTML 構文検証ツール ECMAX に実装 既存のツールと比較実験 今後の課題 計算精度の向上 条件式の値を考慮 値の範囲を特定 ECMAScript に加えた制限を緩和 関数への対応 オブジェクトへの対応

不定値を含む演算 不定値を含む演算は、不定値を返す 型の情報はできる限り残す 例: 不定数値 + 1 ⇒ 不定数値 不定値 == 不定値 ⇒ 不定真偽値 不定文字列 + 1 ⇒ 連結文字列(不定文字列, 1)