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