Vol. 45

情報処理学会論文誌

No. 8

Aug. 2004

インラインスクリプトを含んだ XHTML 文書に対するデータフロー解析を用いた構文検証手法
松 下

誠†

和 則††

鷲 尾

井 上 克 郎†HTML や XHTML 文書の多くは，JavaScript や PHP といったスクリプトを用いて動的に文書の内容を生成することが多い．これらの文書に対して，従来の構文検証手法はスクリプトの内容は無視されていたため実際には構文誤りを含む文書を含まない文書と誤って判断していた．そこで
本研究では，インラインスクリプトとして ECMAScript を含む XHTML 文書の構文を検証する
ために，出力文のデータフロー解析を用いて出力文字列を正規表現を用いて表記し，それに対して検証するという手法を提案する．また，本手法を用いた構文検証ツールの実装を行い，実際の文書をツールに適用して手法の評価を行った．その結果，既存の検証ツールでは検出できなかった誤りを検出できることを確認した．

Data-Flow Based Syntax Validation Method for XHTML Documentswith Embedded Inline Scripts
Makoto Matsushita,† Kazunori Washio†† and Katsuro Inoue†
Today many HTML and XHTML documents are often dynamically generated by scripts
such as JavaScript and PHP. The existing verification techniques cannot be applicable to thesescripts. In order to verify the syntax of an XHTML document containing an in-line script,
we propose a technique that we use the data flow analysis of the output sentences, create
pattern of the output strings, and verify the pattern. In addition, we have been implemented
the syntax verification tool using this technique, and we have evaluated our approach. As
a result, we could find errors which have not been detected by the existing syntax analysis
tools.

によって記述されるプログラム (インラインスクリプ

1. は じ め にト) によって記述されているものとする．

XHTML 文書の内容は XHTML のタグ付け規則(Document Type Definition: DTD) によって定義されている．このため，DTD に違反したタグ付けが行われた場合には，XHTML ブラウザによって正しく表近 年 ，情 報 の 可 搬 性 や 構 文 の 単 純 さ な ど の 観 点から，eXtensible Hyper Text Markup Language(XHTML)1) を用いた文書が多く作成されている．一
般的に，XHTML 文書は「静的コンテンツ」と「動的コンテンツ」の 2 種類の内容で構成されている．ここ

示ができないなど，文書を利用する場合に大きな支障

で静的コンテンツとは、XHTML で定められた構文のをきたす．このため，XHTML 文書が DTD の定義にみで記述された内容が変更されないものであり，動的

反しないように記述されているかどうかを検証するのコンテンツとは、文書を閲覧する環境に依存して変化は非常に重要である．

する内容であり，XHTML とは独立に定義された言語

動的コンテンツの多くは，単純なテキスト情報だけ
ではなく，XHTML で定められたタグをも含む内容である．このため，もしインラインスクリプトを誤って† 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
Department of Computer Science, Graduate School ofInformation Science and Technology, Osaka University†† 大阪大学大学院情報科学研究科コンピュータサイエンス専攻，
現在は三菱電機先端技術総合研究所．
Department of Computer Science, Graduate School ofInformation Science and Technology, Osaka University,
now in Advanced Technology R&D Center, Mitsubishi
Electric Corporation

記述した場合，一見 XHTML 構文誤りを含まない文書であっても，動的コンテンツの出力する内容によって文書全体が構文違反となる可能性がある．しかし，既存の XHTML 構文検証手法は，XHTML 文書の内
容のうち静的コンテンツのみを対象とした検証であり，
動的コンテンツは単なるテキストデータとみなされる．
1

情報処理学会論文誌

2

Aug. 2004

このため，本来構文誤りを含む XHTML 文書を構文として，誤って構造が記述された文書は，受け手が文誤りのない文書と誤認することがあるため，検証結果書の意味を誤解したり，内容が読みとれないなどといっの信頼性が低くなっていた．

た問題が発生することがあげられる．このことから，そそこで本研究では，動的コンテンツとして EC-の構文を検証するシステムが数多く存在している．しMAScript で記述されたインラインスクリプトを含んだ XHTML 文書に対して，動的コンテンツの内容をかし，既存の検証システムは，インラインスクリプト

2)の内容は単なる文字列データと見なし，その内容まで考慮した構文検証手法の提案を行う ．本手法ではま検証しない．したがって，インラインスクリプトが誤っず，対象となる XHTML 文書を静的コンテンツと動た構文の文書を生成しても，これらの検証システムは的コンテンツを分割する．次に，動的コンテンツとし構文誤りを判断ができない．このため，インラインスて記述されているインラインスクリプトに含まれていクリプトの内容も検証するシステムが必要となる．

る，文字列の出力を行う文 (以降，出力文) 中の変数

我々が以前提案したように5) ，入力として適当なデーに対し，データフロー解析と構文解析を行う．両方のタを与えてインタープリタを介すれば，インラインス

解析結果を組み合わせ，動的コンテンツが出力する内クリプトが生成する文書も含めて検証することが可能

容を正規表現を用いて記述する．さらに，静的コンテである． しかし，テストデータによって実行結果が変ンツを解析することによって得られるタグ情報と，動わるため，検証結果も変わる可能性がある．よって全的コンテンツから得られたタグ情報を結合した結果かての実行経路を通るテストデータによって検証を行う

ら，文書全体のツリーを生成し，このツリーに対して必要があるが，そのようなテストデータを作成するこ

DTD に照らした構文検証を行う．また，本手法を用いた XHTML 構文検証ツール ECMAX の実装を行とは一般的に困難である．

い，実際に利用されている XHTML 文書の検証実験を通じて，本手法の有効性評価を行う．

2. 構造化文書とインラインスクリプト

3. 関 連 研 究
動的に生成される HTML 文書や XML 文書について，その構文を検証する研究がいくつか行われている．

本章では，構造化文書を記述するマークアップ言語

Claus Brabrand らは <bigwig>6) という HTML文書や XML 文書を生成するためのスクリプト記述言

およびインラインスクリプトについて説明する．また，語を対象として，スクリプトが動的に生成する HTML

インラインスクリプトを含んだ構造化文書の構文検証(XHTML) 文書の構文検証を行った．
Martin Kempa, Volker Linnemann は DOM7) を拡張し，DOM 自身に構文の正しさを保証する仕組みを持たせた V-DOM と，V-DOM 用の XML 処理言についても触れる．

2.1 XHTML
Hyper Text Markup Language (HTML)3) はウェ
ブページ作成のために，W3C が標準化したマークアッ語である P-XML8) の提案を行った．

プ言語であるが，タグの省略が可能など厳密にその構文を用いて定めた言語が XHTML である．XHTML は

Erik Mejier, Mark Shields は XML 処理用の関数型言語 XMλ9) を開発した．また，細谷晴夫，Benjamin Pierce は XML 処理のための型付き関数型言
語 XDuce10) を開発し，型チェック機能を導入しプロ

タグの省略が不可能である等，厳密な言語定義がなさ

グラムが生成する XML 文書について構文の正しさをれており，近年のウェブページ作成時における標準言保証するようにした．

が定義されていないため構文の曖昧さが存在した．そこで W3C が既存の HTML と仕様が等価な言語を XML語となっている．

2.2 ECMAScript

いずれの研究も，XML 文書や HTML 文書を生成するために新しい言語を作り，その言語に構文の正し

ECMAScript4) は，JavaScript をもとに European
Computer Manufacturer Association (ECMA) にさを保証するような仕組みを構築している．しかし，プ

よって標準化されたインラインスクリプト用言語であ

まざまな XHTML 文書で利用可能である実用的な手る．ブラウザに固有のメソッドなどを排除したものと法とはいえない．

なっている．

2.3 検証の難しさ

ログラム言語として独自の言語を対象としており，さ4. 提案する検証手法

一般的に，構造を持つ文書は，定められた構文に従っ提案する検証手法は，XHTML の構文を定義したて正しく記述されていることが重要である．その理由

DTD と，XHTML 文書を入力として，文書を DTD

Vol. 45

No.
インラインスクリプトを含んだ
8
XHTML 文書に対するデータフロー解析を用いた構文検証手法

3

フェーズ1
抽出

XHTML解析

静的タグ情報 インライン
スクリプト

A*(B|C)

生成

正規表現記述検証

解析

表示 ツリー

DTD

結果

フェーズ2

XHTML文書

データフロー
出力内容の分析

動的タグ情報1:a=1;
2:b=2;
3:c=a+1;

定義
参照

位置 変数
1
2
3

a
b
c

図 2 データフロー解析
Fig. 2 Data flow analysis

フェーズ3

図 1 検証手法の流れ
Fig. 1 Work flow of validation technique

4.1 フェーズ 1: 静的コンテンツ解析
本フェーズでは XHTML 文書の構文解析を行う．イ
ベント駆動型の XML パーサを用いて構文解析を行い，に照らして静的な検証を行う．検証の結果，構文違反

XHTML タグの要素名や属性リスト，テキスト要素にが文書中に存在したかどうか，また違反 ga 存在する

含まれる文字列の情報 (以降，タグ情報と呼ぶ) と，そ

場合にはその場所についての情報を出力として得る．

れらの XHTML 文書上での位置情報を取得する．

具体的には，XHTML 文書中に含まれている，その4.2 フェーズ 2: 動的コンテンツ解析

文字列出力が正規表現として表わされる ECMAScript

本フェーズでは，以下の手順でインラインスクリプ

インラインスクリプトを対象に検証を行う．一般的に，

トの解析を行う．まず，インラインスクリプトの構文

プログラムが出力する文字列を正規表現で表すことは

解析および意味解析を行う．次に，出力文に含まれるできないが，本手法の目的が XHTML の文書と付随変数に対してデータフロー解析を行う．最後にデータするプログラムの出力をあわせて，正規表現として表フロー解析から得た変数の値をもとに，出力される文現される DTD に照らした検証を行うことであるため，字列を，構文解析で得られた制御構造により正規表現

正規表現で表現できる範囲のみを対象としても問題とを用いて表す．

出力文字列を正規表現を用いて表すため，可能性のあ

4.2.1 構文解析および意味解析
ECMAScript の言語仕様4) をもとにインラインス

るすべての実行経路を検証できる．ただし，動的に変クリプトの構文解析を行い抽象構文木を作成する．ま数の値が決定され，それが出力に影響を与える場合，静た，同時にインラインスクリプトの意味解析を行う．こ

的な検証は行えない可能性がある．この場合，本手法の時，抽象構文木の各ノードに対して，インラインス

はその部分についてプログラムの出力が定まらないも

クリプト上での位置情報も記録する．

はならないと考えている．本手法は動的に変わりうる

4.2.2 データフロー解析のとして扱う．
本手法の概略を 図 1 に示す．この手法は大きく分けて次の 3 段階からなる．
フェーズ 1: 静的コンテンツ解析

データフロー解析では，インラインスクリプトに含まれる変数の代入および参照関係の解析を行う．例えXHTML 文 書 のば 図 2 の左側に示されるインラインスクリプトの場

静的コンテンツについて構文解析を行い，タグ情報

合，まず，1 行目を解析して，位置 1 で変数 a が定義とインラインスクリプトを抽出する．

されていることを変数表 (図 2 右側) に記録する．2 行

フェーズ 2: 動的コンテンツ解析

ECMAScript で目も同様に解析し，位置 2 で変数 b が定義されている

記述されているインラインスクリプトの解析を行う．

ことを記録する．次に 3 行目の解析が行われると，代

これは構文解析及び出力文に含まれる変数のデータ

入文の左辺で参照される変数 a の定義を変数表から探フロー解析が含まれる．それらの結果を元に，繰りす．その結果，1 行目であることがわかるため，1 行

返し (*) および選択 (|) 記号を用いた正規表現とし

目から 3 行目に対してデータフローが存在することがて出力文字列を表現する．

わかる．これを順にプログラムの先頭から繰りかえす

フェーズ 3: 構文検証 最後に，フェーズ 2 で得られことによって，依存グラフ11) を作成する．

た正規表現を解析し，タグ情報を生成する．その後

4.2.3 正規表現を用いた出力文字列の表記

フェーズ 1 で得られたタグ情報と合わせて，文書を正規表現による表記とは，インラインスクリプトの要素の親子関係として表したツリーを生成し，DTD

出力文字列を，正規表現のメタ文字を含む文字列で表の要素定義に基づいて構文の検証を行う．

したものである．例えば if 文の条件分岐により，一方

以下，3 つのフェーズについて順に説明する．

の実行経路では “A” という文字列が出力され，他方の実行経路では “B” という文字列が出力されるとする．

情報処理学会論文誌

4

Table 1

表 1 DTD での繰返し定義
Definition of repeatable element in DTD
a?
a*
a+

Aug. 2004
1.
2.
3.
4.

0 回もしくは 1 回
0 回以上
1 回以上

この場合，選択記号の | を用いて，”A | B” と表すことにより，両方の出力結果を 1 つの正規表現で表記する．同様に while 文や for 文の繰り返し中に “C” という文字列が出力される場合には，繰り返し記号の *を用いて，“C* ” と表す．

5.

依存グラフを解析することにより，文字列を出力す

こで出力文が取りうる引数として，基本型 (数値，文字列，null, undefined) およびオブジェクトの定数と変数があるが，オブジェクト (配列を含む) を引数に取った場合，ブラウザやインタープリタが行う処理の結果は動作時にのみ決定される．このため，静的な解析を行う本手法では単なる文字列として扱う．さて，解析の結果，変数の値が静的に決まる場合にはその値を，動的に決まる場合には不定値とする．なお，クラスライ
ブラリを用いた処理が含まれる場合，クラスライブラ
リ内での処理は解析対象としないため，同様に不定値とする．この解析を行う際に用いられる，任意の出力文に出現する変数に対してその値の候補を計算するア

P := C;}else if (C が終了タグである) {if (P と要素名が不一致) エラー;
P := P の親要素;}/* テキストおよび空要素 */else {
P の子要素に C を追加;}
if (スタックが空でない) goto 3;

図 3 ツリー生成アルゴリズム
Fig. 3 Algorithm of creating tree

る文 (以降，出力文) に含まれる変数から，上記のような正規表現を含む出力文字列を得ることができる．こスタックからルート要素開始タグを POP;P := ルート要素;
C := スタックからタグ情報を POP;
if (C が開始タグである) {P の子要素に C を追加;



1:<html>2: <head><title>sample</title></head>
3: <body>
4:<script>
5:
var a = "good morning";
6:
var b = "good afternoon";7:
var date = new Date();8:
document.write("<ul>");9:
if (date.getHour() < 12)10:
document.write("<li>"+a+"</li>");11:
else document.write(b);12:documaent.write("</ul>");13:</script>
14: </body>
15:</html>



図 4 サンプルコード
Fig. 4 Sample code

ルゴリズムについては付録 A.1 にて述べる．

4.3 フェーズ 3: 構文検証て，選択文と同様の処理を行う．

フェーズ 3 ではフェーズ 2 で得られた出力文字列か正規表現の包含関係判定問題を解決することで，検らタグ情報を解析し，フェーズ 1 で得られたタグ情報証を行うところであるが，この検証には指数時間かかと合わせて XHTML 文書の構文検証を行う．本フェーることが分かっている12) ．しかし，DTD で用いられ

ズでは，1) 正規表現で表された文字列からタグの情報

る繰り返しの記述は表 1 のように限定されている．そを解析し，2) フェーズ 1 で得られたタグ情報と合わせのため，たかだか 0,1,2 回の繰り返しを試してどれでて，文書全体のツリーを生成する．そして，3) このツも問題なければ，3 回以上の繰り返しについては試さなリーについて，DTD の要素定義と検証することで構くても良い．よって，ここで解析時に繰返し文を複数文の検証を行うという 3 つの手順を経る．以下，各手の選択文と同様に扱っても正確性を損なうことはない．

順について説明する．

4.3.1 出力文字列の解析
ここでは，フェーズ 2 で得られた出力文字列について，そこからタグ情報を得るための解析を行う．

• 基本文の処理
XML 字句解析を行う．タグ情報をスタックに積む．
• 選択文の処理

4.3.2 ツリーの生成
XHTML 構文解析で得られたタグ情報と出力文字列を解析して得られたタグ情報を組合せて，要素の親子関係を表したツリーを生成する．ツリーを生成するアルゴリズムを図 3 に示す．ただし，以下，図 4 のコードを例にして説明する．
前段階での解析結果より，本アルゴリズムへは 図 6

それまでのスタックを分岐の数だけ複製し，すべにあるように，2 つの場合についてそれぞれ本アルゴての分岐について基本文と同じ処理を行う．

リズムが適用される．これは，図 5 には 1 つの選択• 繰返し文の処理繰り返しが 0 回，1 回, 2 回のいずれかであるとし記号が含まれているためであり，本手順によってそれぞれツリーが生成されることとなる．1 つめの入力を

Vol. 45

No.
インラインスクリプトを含んだ
8
XHTML 文書に対するデータフロー解析を用いた構文検証手法

5




"<ul>",(("<li>","good morning","</li>")| "good afternood"),"</ul>"
図 5 出力文字列
Fig. 5 Pattern of output stringLine 11: DTD violation found.
Appearance: #PCDATA
Requirement: li+
Data-Flow: Line 6, Line 11
図 9 検証結果例
Fig. 9 Exmaple of validation result"<html>","<head>","<title>","sample","</title>","</head>","<body>","<ul>","<li>","good morning","</li>","</ul>","</body>","</html>"



たどり，出力に関係する全てのノードとその位置を特定する．特定した結果を DTD に違反する内容として
返す．


4.4 検 証 例"<html>","<head>","<title>","sample","</title>","</head>","<body>","<ul>","good afternoon","</ul>","</body>","</html>"


図 6 出力文字列と静的 XHTML タグの結合結果
Fig. 6 Join results of static XHTML tags and script
output

ここでは，午前中に実行すると DTD 違反とはならないが，午後に実行すると違反となるような，図 4 に

 示すインラインスクリプトを例にして，提案する検証
手法を適用した結果を示す．まず，インラインスクリ
プトの出力文字列を正規表現で表したものは，図 5 となる．この出力文字列を解析し，静的なタグ情報と合html

わせてツリーを生成すると，図 7 に示す 2 つのツリーhtmlが生成される．各ツリーに対して検証アルゴリズムを
head

body

head

body

title

ul

title

ul

では ul 要素の子要素であるテキスト要素に DTD 違

text

li

text

text

反があることがわかる．よって，このインラインスク

text
図 7 生成されたツリー
Fig. 7 Created tree

適用すると，左のツリーでは違反がなく，右のツリー

リプトの出力結果は DTD に違反していると判定され，違反が含まれる場所を結果として得られる (図 9)．このように，本手法ではテストデータを用意することな
くすべての実行経路について検証を行えるため，DTD

1.
2.

element := ルート要素;
if (element が子要素を持っている) {children := element の子要素;
definition := element の内容モデル;
if (children が definition にマッチしない)
DTD 違反;element := children;
goto 2;}

図 8 ツリー検証アルゴリズム
Fig. 8 Algorithm of validating tree

違反を容易に発見することができる．

5. 実

装

5.1 ツール ECMAX の概要
先に述べた検証手法を用いて，ECMAScript で記述されたインラインスクリプトを含む XHTML 文書
に対する構文検証システム ECMAX の試作を行った．
開発環境は以下の通りである．

本アルゴリズムに適用することにより，図 7 の左側ツリーが，また 2 つめの入力によって図 7 の右側ツリーが得られる．

4.3.3 ツリーの検証生成された各ツリーに対して，DTD に照らした検証を行う．検証アルゴリズムを図 8 に示す．すべてのツリーに対して検証を行い，DTD 違反がなければ，その XHTML 文書の構文は正しいという結果を示す．
もし DTD 違反が発見された場合は，その要素が• CPU: Pentium4 2GHz
• RAM: 2GB• OS: FreeBSD 4.7–RELEASE• 言語: Java (約 9,000 行)
5.2 ECMAX の構成
ECMAX の構成を 図 10 に示す．本システムは GUI,XML 解析部，ECMAScript 解析部，出力文字列作成·解析部，検証部から成る．
ユーザーは GUI を通して XHTML および DTD

XHTML 文書中のどの位置に存在しているかを特定すを入力し，GUI は検証結果を表示する．

る．もし動的コンテンツ内にその要素が含まれる場合

XML 解析部では，入力として XHTML 文書を受け取り，構文解析を行う．具体的には，SAX パーサをには，依存グラフ上でその要素からグラフを逆向きに

情報処理学会論文誌

6

GUI

Aug. 2004

XML解析部
XHTML / DTD

ユーザー
検証部
ツリー

要素定義

ツリー作成部
静的タグ情報インラインスクリプト

動的タグ情報ECMAScript解析部

出力文字列作成・解析部
AST / フローグラフ

図 10 検証システムの構成
Fig. 10 Structure of validtion system

用いて XHTML 文書の構文解析を行い，タグの名前
や属性，テキスト内容を得る．また，XHTML 文書中

図 11 ECMAX の実行画面
Fig. 11 Screenshot of ECMAXの script 要素から ECMAScript の記述を得る．さら
に，DTD を構文解析して要素の定義を取得する．

ECMAScript 解析部では，入力として XML 解析部で得られたインラインスクリプトを受け取り，構文解析およびデータフロー解析を行って，抽象構文木および依存グラフを作成する．
出力文字列作成部では，インラインスクリプトの抽
象構文木および依存グラフを受け取り，出力文字列を生成する．出力文字列解析部では，得られた出力文字

表 3 htmllint で無違反だった文書の ECMAX での検証結果
Table 3 Valition result of judged “no error” by htmllint
DTD

StrictTransitional

スクリプト構文違反
スクリプト内 XHTML 構文違反
スクリプト内タグを含むタグ付け違反
DTD 違反
違反なし

13
13
9
34
0

46
42
16
63
47

合計

69

214

列からタグ情報を作成する．
ツリー作成部では，XML 解析部で得られた XHTMLているもの 232 個を収集した．さらに変換ツールをタグ情報と，出力文字列解析部で得られたインライン

用いて HTML から XHTML へ変換した．具体的にスクリプトのタグ情報を受け取り，それぞれのタグ情は，XHTML1-Strict DTD 準拠の文書と XHTML1Transitional DTD 準拠の文書をこの変換によって得た．
6.2 実 験 方 法報を統合して文書全体のツリーを作成する．
検証部ではツリーをルート要素から辿りながら，その要素の子要素が定義と一致しているか検証する．親子すべてのサンプルデータに対して，XHTML 構文

関係に誤りがあればそれは DTD 違反としてユーザー

チェックおよび ECMAScript 構文チェックを行った．

に警告を通知し，誤りがなければ正しい文書であるこ

その上で，インラインスクリプトの内外を含めたタグとをユーザーに通知する．

の対応づけのチェックを行った．さらに，構文に誤り

5.3 ECMAX の実行例がなかったサンプルデータに対して，対応する DTD

図 4 の文書に対して，ECMAX を用いて検証した(Strict DTD もしくは Transitional DTD) を用いて，DTD と文書との整合性について検証した．また，既存の XHTML 検証ツール htmllint (2001 年 9 月 11日版) を用いて，元の HTML 文書を入力として検証

実行画面を図 11 に示す．DTD 違反が発見されており，DTD 違反を起こす可能性のある実行経路が反転表示されている．

6. 評 価 実 験を行った．

6.3 実 験 結 果

本章では，ECMAScript で記述されたスクリプトを実験結果を表 2 に示す．括弧内の数値は，不定値を含む XHTML 文書に対して ECMAX を用いて構文

XHTML のタグが一切含まれていないテキストとみなの検証を行い，その検証結果から本手法の評価を行う．

して処理を行った部分に何らかの違反が含まれていた

6.1 実 験 対 象

文書，あるいは，違反なしという結果を得た文書のう

実験対象として，Web サイト上公開されている文書

ち，そのような不定値が含まれていた文書の数，であのうち，出力文を用いて HTML 文書を動的に生成しる．さらに htmllint では違反が検出されなかった文書

Vol. 45

No.
インラインスクリプトを含んだ
8
XHTML 文書に対するデータフロー解析を用いた構文検証手法

7

表 2 ツールによって検出された XHTML 文書数
Table 2 Number of XHTML documents found by tools
ツール

DTD

ECMAX
StrictTransitional

XHTML 構文違反
スクリプト構文違反
スクリプト内 XHTML 構文違反
スクリプト内タグを含むタグ付け違反
DTD 違反違反なし

113 (35)0

合計を ECMAX で検証した結果は 表 3 の通りである．

1048
43 (14)18 (14)65 (12)48 (23)

Stricthtmllint
Transitional

153
69

10
—
—
—
8
214

232 (63)232の出力へ，動作時にのみ決定される文字列が含まれて「XHTML 構文違反」はスクリ
なお，表 2 において，

おり，かつその部分に XHTML 構文要素とみなされプト以外の部分に閉じた構文違反があり 図 10 で述べる文字列がある場合には，構文検証を正しく行えない．

「スクリ
た XML 解析部が違反を検出したものである．

具体的には，動作時にのみ決定される文字列に含まれプト構文違反」はスクリプト自体に ECMAScript 構ている XHTML 構文要素を含めて，全体として正し

文エラーがあり，ECMAScript 解析部が違反を検出しい構文であるような XHTML 文書を，本手法では誤たものである．
「スクリプト内 XHTML 構文違反」はりを含む文書として判断されてしまう．構文検証の精スクリプトの出力文字列内で閉じた XHTML 構文違

度を向上させるためには，本手法で提案する静的な解反があり，出力文字列生成・解析部が違反を検出したも析に加え，実行時の情報を用いた解析が必要であろう．

のである．
「スクリプト内タグを含むタグ付け違反」は，
スクリプトの出力を含んだ文書全体が XML 文書とし

7. ま と めて (DTD に依らず) 構文違反を含んでおり，ツリー作

本研究では，ECMAScript で記述されたインライン

成部が違反を検出したものである．
「DTD 違反」は，上スクリプトを含む XHTML 文書を対象として，DTD記のすべての違反が全く含まれていないが，DTD にに基づいた構文であるかを検証するための手法を提案

照らして検証を行った場合に違反があるもので，検証した．本手法は，スクリプトの出力文に対してデータフ部によって違反を検出したもの，である．検証作業は

ロー解析を行い，出力文字列を正規表現を含む文字列で

これら 5 つについて順番に行われ，どこか 1 箇所で違表した上で，その文字列の検証を行うものである．また，

反が発見された場合には，そこで解析を終了している．

本手法に元づく検証システムを試作し，インターネッ

6.4 考
察
図 2 および図 3 から，ECMAX に htmllint が発見

ト上に存在するインラインスクリプトを含む XHTML

しなかった多くの違反を発見できていることがわかる．

の結果，動的コンテンツの内容を考慮した解析によっ

また，ECMAX によって Transional DTD による検て，文書の構文間違い等をより多く発見できることが証の結果「違反なし」とされた 48 の文書のうち，47わかった．

文書に対して検証を行い，本手法の評価を行った．そについては htmllint も「違反なし」という検証結果

今後の課題としては，ECMAScript 言語が提供すを出力しているが，残る 1 つについては htmllint はるライブラリへの対応，変数のエイリアス解析，XMLDTD 違反であると誤って検出した．これは，htmllint

Schema への対応などがある．

がインラインスクリプトの出力を考慮できなかったことによるものである．本手法によるインラインスクリ
プトの出力結果を考慮した検証によって，より正確な検証結果を得ることができると考えられる．
また，不定値を含む文書は全体の 3 割程度 (232 中
63) であり，その他の文書はタグを静的に記述し，メッ
セージを動的に生成するという文書であった．したがって，本手法の適用範囲は広範囲に及ぶものであり，本手法の有効性は高いと考えられる．
しかしながら，本手法は静的な解析を行っているた
め，ECMAScript で記述されたインラインスクリプト

参 考

文 献

1) W3 Consortium: XHTML 1.0: The Extensible
HyperText Markup Language, A Reformulation of HTML 4.0 in XML 1.0. Working Draft,
http://www.w3 .org/TR/1999 (1999).
2) 鷲尾和則, 松下誠, 井上克郎: JavaScript を含んだ HTML 文書に対するデータフロー解析を用いた構文検証手法の提案, 電子情報通信学会研究技術報告, Vol. SS2002-22, pp. 13–18 (2002).
3) W3 Consortium: HTML 4.01 Specification(1999). http://www.w3.org/TR/1999/REC-

情報処理学会論文誌

8
1.
2.
3.

4.

スクリプトを構文解析，意味解析;
program := スクリプトの抽象構文木;
node := program のルートノード;
if (node = 繰返し制御構造文) 繰り返し記号 “*” を追加;
else if (node = 選択制御構造文) 選択記号 “|” を追加;
else if (node = 出力文) {引数に対してデータフロー解析，値を求める;
if (変数の値が動的に決まる) 値 := 不定値;
else
値 := 定数値;
値を追加;

録A.1 変数値候補の計算アルゴリズム
A.1.1 概要依存グラフから変数値の候補を計算するアルゴリズ

var a=10;
for (var i=0; i<10; i+=1) {a += i;}document.writeln(a);
図 13 ソースコードの例
Fig. 13 Example of source code1
3
var a=10; i<1024var i=0a+=i;

変数値候補の計算アルゴリズム
Algorithm of creating pattern

html401-19991224.
4) ECMA: ECMAScript Language Specification (1999). http://www.ecma.ch/stand/ecma262.htm.
5) 鷲尾和則, 松下誠, 井上克郎: JavaScript を含む
HTML 文書の妥当性検証手法の提案, 電子情報通信学会総合大会講演論文集, Vol. D-3-5, p. 31(2002).
6) Brabrand, C., Møller, A. and Schwartzbach,M.: Static validation of dynamically generated
HTML, Proceedings of Workshop on Program
Analysis for Software Tools and Engineering(PASTE 2001), Snowbird, Utah, USA (2001).
7) W3 Consortium: Document Object Model(DOM) Level 1 Specification, Version 1.0. Recommendation (1998).
http://www.w3.org/
TR/1998.
8) Kempa, M. and Linnemann, V.: V-DOM and
P-XML - Towards Valid XML Applications(2002).
9) Meijer, E. and Shields, M.: XMλ: A Functional Language for Constructing and Manipulating XML Documents (1999). (Draft).
10) Hosoya, H. and Pierce, B.C.: XDuce: A Typed
XML Processing Language, Int’l Workshop on
the Web and Databases (WebDB’2000), Dallas,
Texas (2000).
11) Horwitz, S. and Reps, T.: The Use of Program
Dependence Graphs in Software Engineering,
14th International Conference on Software Engineering, Melbourne, Australia (1992).
12) Seidl, H.: Deciding Equivalence of Finite
Tree Automata, SIAM Journal on Computing,Vol. 19, No. 3, pp. 424–437 (1990).

付

}if (node が子ノードを持っている) {node := node の子ノード;
goto 3;}

図 12
Fig. 12

Aug. 2004

6
document.writeln(a);5i++

図 14 図 13 の依存グラフ
Fig. 14 Flow graph of example code

ム (図 12) について説明する．本アルゴリズムは，EC-

MAScript プログラムに含まれる変数のうち，プログ
ラム実行の際動的に決定される変数 (オブジェクト) 以
外を対象として，任意の文中におけるある変数の取りうる値の候補を計算するものである．
依存グラフから変数値の候補を計算するアルゴリズ
ム (図 12) について説明する．本アルゴリズムは，いくつかの制約を加えた ECMAScript プログラムを対象として，任意の文中におけるある変数の取りうる値の候補を計算するものである．
本アルゴリズムでは最初に，例えば図 13 のような
ECMAScript のソースコードから，図 14 のような依存グラフを構築する (図 12 の 1)．依存グラフの頂点
は文または式であり，有向辺は始点の次に終点が実行されうることを示す．値を調べたい文に対応する頂点
を対象頂点，値を調べたい変数を対象変数と呼ぶ．
対象頂点を始点とし ((図 12 の 2)，対象変数への代入が見付かるまで，有向辺を逆向きに辿る ((図 12 の

4)．見付かった代入文の右辺に変数がある場合は，その変数の値を再帰的に調べ，右辺の取り得る値を決定する (図 12 の 3)．この手順だけでは，依存グラフに閉路がある場合に，無限に再帰してしまう場合がある．
これを避けるために，調査中の頂点と変数の組を記憶しておき，二重の探索を避ける．
以下，対象頂点 n を実行した直後の対象変数 x の値の候補を xn と表す．値の候補は，具体的な値 (1,”str”, true 等) と，型の決まった不定値 (不定値 (数値), 不定値 (文字列) 等) の集合で示される．探索中の対象頂点と対象変数の組を記憶しておく大域変数を Qとする．xn を求めるためのアルゴリズムは，以下の通
りである．
(1)

Q に， 対象頂点と対象変数の組 (n, x) が含まれて

Vol. 45

(2)

(3)

No.
インラインスクリプトを含んだ
8
XHTML 文書に対するデータフロー解析を用いた構文検証手法

いるか調べる．含まれている場合は，xn を展開せず，そのまま返す．含まれていない場合は，(n, x)
を Q に追加する．
n の種類によって，以下の処理を行う．
対象変数への代入文でない場合 n に入ってくる辺の始点の集合を Nin として，r=∩m∈Nin xmとする．
対象変数への代入文で，右辺が定数の場合 r={ 右辺の値 } とする
対象変数への代入文で，右辺に変数がある場合 右辺に含まれる変数それぞれの値候補を計算する．
右辺の式に，得られた値候補を代入し，r に加える．r の要素に xn を含む式があった場合は，その式に xn を含まない式を代入し，r に加えることを，r の要素が増えなくなるまで繰り返す．ただし，xn の要素として xn 自身が含まれていた場合には，xn の値のうち，具体的な値として求まっている物を代入した上で，その演算結果の型のみを用いて，「不定値 (得られた型)」とする．
Q から (n, x) を削除し，r を返す．

このようにして求められた，出力文に含まれる引数9= { 1, 不定値 (数字) } となる．この結果，i3 の値は
これまでの結果をあわせて {0, 1, 不定値 (数字)} であることがわかる．

a3 と i3 の値が求められたので，a4 の計算を行うことができる．a3 には 2 つ，i3 には 3 つの要素がある
ため，6 つの足し算を行い，その結果を a4 とすることとなる．ただしこの時，不定値 (数字) へ定数の演算を行っても，やはり不定値 (数字) であること，複数の同じ要素は 1 つにまとめることができることから，{10,11, 不定値 (数字), a4 , a4 + 1} を得る．a4 の計算結果中に a4 が再度出現したため，上記の i5 と時と同様に a4 を消去すると，{10, 11, 不定値 (数字)} が得られる．
以上の結果から，a6 = {a1 , a4 } = {10, 11, 不定値(数字)} を得ることができ，これが求める候補となる．
(平成 15 年 10 月 27 日受付)
(平成 16 年 6 月 10 日採録)の値について，抽象構文木の情報から，それぞれの出
力文が if 文や while 文などの制御構造下にある場合，

鷲尾 和則

正規表現で用いられる選択記号 (|) や繰り返し記号 (*)

平成 13 年大阪大学基礎工学部情を付加する．選択記号 (|) を付加する制御構造は，if

報科学科退学．平 15 同大学大学院情文，switch 文である．また，繰り返し記号 (*) を付加

報科学研究科卒．同年三菱電機先端する制御構造は，while 文，for 文である．また，連続技術総合研究所．在学時，XHTML

するそれぞれの出力文字列の間には連結記号 (,) を挿

文書検証の研究に従事．

入する．

A.1.2 具体的な計算例

松下

ここでは，図 13 の最後の行で参照されている変数

誠（正会員）

平 5 阪大・基礎工・情報卒．平 10

a について，その候補 a6 を具体的に求める手順につ同大学大学院博士後期課程退学．同いて説明する．

年同大・基礎工学研究科・助手．平

まず Q = {(6, a)} とした上で，a6 を計算する，依14 同大・情報科学研究科・助手．博士(工学)．ソフトウェア開発環境，ソ存グラフを逆向きにたどることにより，{a1 , a4 } であることがわかる．ここで，a1 = {10} であり，a4 ={a3 + i3 } であることから，次に Q に (4, a) を追加した上で a3 を求める．a3 = {a1 , a4 } であるが，ここで (4, a) が Q に含まれていることと，すでに a1 の値が求まっていることから，a3 = {10, a4 } として a3の計算を終える．
次に i3 を求める．これは i2 , i5 となるが，ここで i2は {0} であり，i5 = {i4 + 1} であることから，Q へ(5, i) を加えて i4 の値を求めることとする．i4 の値は{i2 , i5 } であるが，(5, i) は Q に含まれていたためこ
こで計算を終了し，既知の結果とあわせて，i5 = { 1,i5 + 1 } となる．この時，左辺の i5 は消去できて，i5

フトウェア開発プロセス，オープンソース開発の研究に従事．
井上 克郎（正会員）
昭 54 阪大・基礎工・情報卒．昭 59
同大大学院博士課程了．同年同大・
基礎工・情報・助手．昭 59〜昭 61 ハ
ワイ大マノア校・情報工学科・助教
授．平 1 阪大・基礎工・情報・講師．
平 3 同学科・助教授．平 7 同学科・教授．工博．ソフ
トウェア工学の研究に従事．