インラインスクリプトに対するデータフロー 解析を用いた XHTML 文書の構文検証 k-wasio@ics.es.osaka-u.ac.jp
背景 HTML文書 インラインスクリプト インターネットの普及によりHTML文書が多数作成されている DTD(文書型定義)にタグ付け規則が定義されている インラインスクリプト HTML文書にインラインスクリプトを記述することが多々ある インラインスクリプトは任意の HTML 文書の断片を出力することが可能 既存のHTML構文検証ツールはスクリプトの内容を無視する 平成14年度 修士論文発表会
目的 正しいHTML文書をやりとりするために，その構文検証を行う必要がある 既存の検証ツールではスクリプトの内容は無視される タグ付け規則通りに正しく記述されているか 平成14年度 修士論文発表会
アプローチ 動的解析法 静的解析法 静的解析法を利用 スクリプトを実行して得られた結果を利用 正確な実行結果が得られる 実行結果が変わりうる（検証結果が変わりうる） 静的解析法 実行経路を特定せずすべてのパスで解析を行う すべてのパスでの解析が可能 動的に値が定まるものは解析不能 静的解析法を利用 すべてのパスにおいて検証できなければならない 動的に値が定まるものは不定値として解析する 平成14年度 修士論文発表会
提案手法の概要 対象 基本方針(静的解析法) 入出力 マークアップ言語: XHTML スクリプト記述言語: ECMAScript スクリプトの出力文字列を正規表現を用いてパターン化する 選択 A|B (AまたはB) 繰り返し C* (Cの繰り返し) パターンについて検証を行う すべてのパスについて検証することができる 入出力 入力: ECMAScript を含む XHTML 文書 出力: 検証結果 平成14年度 修士論文発表会
検証手法 フェーズ１： XHTML文書解析 フェーズ２： スクリプト解析 フェーズ３： 構文検証 A*(B|C) 構文解析 抽出 パターン化 タグ情報 ECMAScript A*(B|C) 生成 パターン 生成 検証 ツリー DTD タグ情報 結果 平成14年度 修士論文発表会
XHTML文書解析 -フェーズ１- XHTML文書についてXML構文解析を行う 構文解析結果はタグ情報 タグの出現順，テキスト内容など スクリプトはテキストデータ A*(B|C) 平成14年度 修士論文発表会
スクリプト解析 -フェーズ２- スクリプトに対して解析を行う Step1: 構文解析・意味解析 Step2: データフロー解析 A*(B|C) 平成14年度 修士論文発表会
構文解析/意味解析 –フェーズ２:Step1– ECMAScriptの言語仕様†に基づいて字句解析と構文解析を行う 解析結果は抽象構文木 抽象構文木に対し意味解析を行う A*(B|C) †ECMA - Standardizing Information and Communication Systems, Standard ECMA-262, ECMAScript Language Specification, 3rdedition, http://www.ecma.ch/ecma1/STAND/ECMA-262.HTM, December 1999. 平成14年度 修士論文発表会
データフロー解析 –フェーズ2:Step2– 変数の代入・参照関係の解析 抽象構文木をルートから順に辿りながら フローグラフを構築 1: a = 1; 2: b = 2; 3: c = a+1; 行 変数 1 a 2 b 3 c 定義 データフロー A*(B|C) 参照 変数の代入・参照関係の解析 抽象構文木をルートから順に辿りながら 変数が定義された 変数表に追加 変数が参照された 変数表を参照．定義されている位置を判定． フローグラフを構築 頂点:文，辺:データフロー 平成14年度 修士論文発表会
出力文字列のパターン化 –フェーズ2:Step3– パターンとは? if 文の条件分岐 一方の実行経路では ”A” が出力 他方の実行経路では ”B” が出力 双方をまとめて記述する (“A” | “B”) : A または B while文などの繰り返し文 (“C”)* : C の繰り返し A*(B|C) 平成14年度 修士論文発表会
出力文字列のパターン化 –フェーズ2:Step3– 出力文の引数に含まれる変数についてデータフローを得る データフローをもとに引数の値を求める 動的にその値が定まるものは不定値 (変数の型で代用) クラスライブラリを用いた場合不定値 定数値はそのまま 引数の値について 制御構造 if 文など選択文: | を付加 while 文など繰り返し文: * を付加 A*(B|C) 平成14年度 修士論文発表会
構文検証 –フェーズ３– タグ情報生成 ツリー生成 ツリー検証 フェーズ2で得られた出力文字列のパターンからタグ情報を生成する フェーズ1で得られたXHTMLタグ情報と，先ほど得られたスクリプトタグ情報を合わせて，ツリーを生成する ツリー検証 ツリーに対して要素の親子関係を検証する A*(B|C) 平成14年度 修士論文発表会
タグ情報生成 –フェーズ3– 基本文 選択文 繰り返し文 XML字句解析を行う タグ情報をスタックに積む 分岐数だけスタックを複製 それぞれの分岐について基本文と同じ処理を行う 繰り返し文 繰り返し回数を不定とし，0回，1回, 2回の場合について，選択文と同じ処理を行う DTDにおいて用いられる繰り返しの正規表現 ? : 0 回 or 1 回 * : 0 回以上 + : 1 回以上 A*(B|C) 平成14年度 修士論文発表会
ツリー生成 –フェーズ3– タグ情報スタックからタグを pop 開始タグなら現在の要素の子要素に追加，子要素について繰り返す 終了タグなら現在の要素名と比較 異なる要素名なら構文エラー テキスト，空要素なら子要素に追加 不定値はテキストとみなす A*(B|C) 平成14年度 修士論文発表会
ツリー検証 –フェーズ3– ルート要素から順に 検証結果を表示 子要素の並びとDTDの定義(正規表現)をパターンマッチ 子要素について繰り返す 検証結果を表示 A*(B|C) 平成14年度 修士論文発表会
検証例 –あいさつスクリプト– html body ul li text head title “<ul>”, <title>sample</title> </head> <body> <script> var a = “good morning” var b = “good afternoon” Date date = new Date(); document.write(“<ul>”) if(date.getHour() < 12){ document.write(“<li>”); document.write(a); document.write(“</li>”); }else{ document.write(b); } document.write(“</ul>”); </script> </body> </html> “<ul>”, (( “<li>” , “good morning” , “</li>” ) | “good afternoon” ) , “</ul>” html body ul li text head title 平成14年度 修士論文発表会
検証例 –検証内容– DTD違反なし DTD違反あり ul の子要素(テキスト)が違反 <!ELEMENT ul (li)+> html html head body head body title ul title ul text li text text text DTD違反なし DTD違反あり ul の子要素(テキスト)が違反 <!ELEMENT ul (li)+> 平成14年度 修士論文発表会
システムの実装 ECMAScript を含む XHTML 文書の検証システム(ECMAX) の実装を行った 開発環境 CPU: Pentium4 2GHz RAM: 2GB OS: Free-BSD 4.7 言語: JAVA (約9,000行) 平成14年度 修士論文発表会
システム構成 GUI user 検証部 XML解析部 ツリー作成部 パターン解析部 ECMAScript解析部 パターン作成部 XHTML文書/DTD選択 XHTML 文書 DTD GUI 結果表示 user 結果/エラー位置 要素定義 ツリー 検証部 XML解析部 ツリー作成部 タグ情報 タグ情報 スクリプト パターン解析部 ECMAScript解析部 パターン AST・フローグラフ パターン作成部 平成14年度 修士論文発表会
実行例 違反を起こすパス DTD違反検出 平成14年度 修士論文発表会
検証実験 実験データ (232個) 実験方法 Web サイト†から JavaScript を含む HTML文書を収集 ツールを用いて XHTML 文書に変換 実験方法 XHTML およびスクリプトの構文チェック 構文違反がないサンプルに対して XHTML1-Strict DTD で検証 XHTML1-Transitional DTD で検証 既存の検証ツール (htmllint) と比較 †The JavaScript Source (http://javascript.internet.com) 平成14年度 修士論文発表会
実験結果 ツール 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 ()内の数字は不定値をテキストとみなした条件付き検証数 平成14年度 修士論文発表会
考察 htmllint における検証で違反がなかった文書の ECMAX での検証結果 htmllint では検出できなかった違反を検出 DTD XHTML1-Strict XHTML1-Transitional スクリプト構文違反 13 46 スクリプト内XHTML構文違反 42 スクリプト内タグを含めた タグ付け違反 9 16 DTD違反 34 63 違反なし 47 合計 69 214 htmllint では検出できなかった違反を検出 不定値(動的に定まる変数値) 全体の3割程度． 多くは，タグを静的に記述，メッセージを動的に生成 本手法の適用範囲は広い 平成14年度 修士論文発表会
まとめ ECMAScriptを含むXHTML文書について構文検証手法を提案した システムに実装し評価を行った 今後の課題 既存の検証ツールでは検出できない違反を検出できた 今後の課題 関数やライブラリへの対応 エイリアスの解析 XML Schema への対応 平成14年度 修士論文発表会
終 平成14年度 修士論文発表会
本手法の有効性 有効な場合 有効でない場合 出力されるタグが静的に決まる 実行経路が複数存在する 不定値にタグが含まれる（可能性のある）場合 ループなどに動的情報に依存する，タグを含む出力文がある場合 for(i = 0; i < 10; i++) { if (i == 偶数) document.write(“<a>”); else document.write(“</a>”); } 平成14年度 修士論文発表会