XHTML構文検証手法におけるスクリプト要素の静的解析アルゴリズム早瀬康裕†, 鷲尾和則‡, 松下誠†, 井上克郎† † 大阪大学大学院情報科学研究科 ‡ 大阪大学大学院基礎工学研究科 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 背景 HTML文書の普及 HTML文書は、タグ付け規則に従って記述することが必要タグ付け規則に違反したHTML文書は、ブラウザで正しく表示されないなどの問題がある． DTD(文書型定義)にタグ付け規則が定義されている HTML文書へのスクリプト埋め込みスクリプトは任意の HTML 文書の断片を出力することが可能既存のHTML構文検証ツールはスクリプトの内容を無視 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 2 スクリプトによる HTML 生成の例 <span> <script type="JavaScript"> <![CDATA[ var day = new Date(); var message; if(day.getHour() < 12){ message = "good morning"; } else { message = "<div>good afternoon</div>"; } document.write(message); ]]> </script> </span> 午前のとき <span> good morning </span> 午後のとき <span> <div>good afternoon</div> </span> DTD違反変数が取りうる値を知る必要既存のシステムでは script 要素を無視するため、違反を検出できない Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 3 DTD 検証ツール ECMAX スクリプトの出力を考慮した DTD 検証ツールECMAX † XHTML 1.0 ECMAScript (ECMA-262) にいくつかの制限を加えたもの (関数やオブジェクトに非対応) 手順引数に変数が含まれていた場合には、変数が取り得る値を知る必要がある 1. XHTML を解析し、スクリプトを抽出 2. 出力文を探し、出力文の引数が取りうる値を計算 3. 2. の結果と、出力文の属する制御構造 (条件文や繰り返し文) から、出力されうる文字列を計算 4. 3. の結果を、静的な部分と合わせて DTD 検証 † 鷲尾和則, 松下誠, 井上克郎, “JavaScriptを含んだHTML文書に対するデータフロー解析を用いた構文検証手法の提案”, 信学技報, SS2002-22, pp. 13-18, 2002 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 4 フローグラフ ECMAScript プログラムから、フローグラフを作成頂点: 文または式有向辺: 制御が移り得ることを示す 1 m=“abc” m=“abc”; if (x) { m=x; } document.writeln(m); 2 x 3 m=x 4 document.writeln(m) Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 5 候補集合変数が特定の文の実行直後に取り得る値を候補、候補全体の集合を候補集合と呼ぶ候補とは以下のいずれか定数 “abc”, 123, true, undefined, null 等不定値型の分かっているもの String, Numeric, Boolean 型の分からないもの未計算の式式には、候補集合を含む場合がある候補集合は、変数名と頂点番号の組で識別する例:頂点 5 を実行した直後の x の値 ⇒ x5 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 6 候補集合の計算値を調べたい頂点・変数を、対象頂点・対象変数と呼ぶ 1. 対象頂点を起点として、フローグラフの辺を逆向きにたどり、対象変数への代入文を含む頂点を探す 1 2. 見つかった頂点それぞれに対して m=“abc” 2 代入文の右辺に変数を含まないなら、右辺の値を候補集合に追 x 加する 3 代入文の右辺に変数が含まれる場合 m=x その変数の候補集合を計算中でないなら、候補集合を再帰的に計算し、代入した結果を候補集合に追加 4 document.writeln(m) 変数の候補集合を計算中の場合は、変数を候補集合の記号で置き換えた、未計算の式を候補集合に追加 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 7 候補集合の計算 1 m=“abc” m=“abc” a=“abc” 2 値を調べたい頂点・変数を、対象頂点・対象変数と呼ぶ x 3 1. 対象頂点を起点として、フローグラフの辺を逆向きにたどり、 m=x a=x 対象変数への代入文を含む頂点を探す 4 2. 見つかった頂点それぞれに対して document.writeln(m) 代入文の右辺に変数を含まないなら、右辺の値を候補集合に追加する代入文の右辺に変数が含まれる場合その変数の候補集合を計算中でないなら、候補集合を再帰的に計算し、代入した結果を候補集合に追加変数の候補集合を計算中の場合は、変数を候補集合の記号で置き換えた、未計算の式を候補集合に追加 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 8 候補集合を計算中の場合の処理変数の計算中の場合は、変数を候補集合の記号で置き換えた未計算の式を候補集合に追加未計算の式を除去候補集合自身を含まない候補を代入新たな候補が得られたら、不定値とする i1 i3 0 3+ 1 i… 1, 不定数値 i3+1 の i3 に、１を代入 ↓ 2 1 i=0 2 document.writeln(i) 3 i=i+1 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 9 システムの実装と実験変数値候補計算アルゴリズムを、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 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 10 実験結果ツール DTD ECMAX htmllint XHTML1- XHTML1XHTML1- XHTML1Strict Transitional Strict Transitional XHTML構文違反 10 10 スクリプト構文違反 48 -- スクリプト内XHTML構文違反 43 (14) -- スクリプト内タグを含めたタグ付け違反 18 (14) -- DTD違反 113 (35) 65 (12) 153 8 違反なし 0 (0) 48 (23) 69 214 合計 232 (63) 232 ()内は、スクリプトの出力に不定値が含まれていた数 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 11 実験結果ツール DTD ECMAX htmllint XHTML1- XHTML1XHTML1- XHTML1Strict Transitional Strict Transitional XHTML構文違反 10 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 では、スクリプト内での違反も発見できた Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 12 実験結果ツール DTD ECMAX htmllint XHTML1- XHTML1XHTML1- XHTML1Strict Transitional Strict Transitional 出力に不定値が含まれた場合、その中にはタグは無いと仮定している 10 10 XHTML構文違反 ⇒ 検証結果は確実ではない 48 -スクリプト構文違反スクリプト内XHTML構文違反 43 (14) -- スクリプト内タグを含めたタグ付け違反 18 (14) -- DTD違反 113 (35) 65 (12) 153 8 違反なし 0 (0) 48 (23) 69 214 合計 232 (63) 232 ()内は、スクリプトの出力に不定値が含まれていた数 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 13 実験結果の考察スクリプトを考慮することで、既存のシステムが見逃していた違反を発見できた正しい XHTML 文書作成を補助できる約1/3のデータで、出力に不定値が含まれていた不定値を含む検証は、確実ではない不定値を減らすため、計算精度の向上が必要 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 14 まとめと今後の課題まとめ ECMAScript プログラムで、変数が取りうる値を計算する手法について説明 XHTML 構文検証ツール ECMAX に実装既存のツールと比較実験今後の課題計算精度の向上条件式の値を考慮値の範囲を特定 ECMAScript に加えた制限を緩和関数への対応オブジェクトへの対応 Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 15