使用程序分析和特征識別方法過濾網(wǎng)頁廣告

何欣程，查春柳，2，許 蕾，2

1 (南京大學 計算機科學與技術(shù)系，南京 210023)2 (南京大學 計算機軟件新技術(shù)國家重點實驗室，南京 210023)

1 引 言

在互聯(lián)網(wǎng)時代，用戶可以免費訪問各種網(wǎng)站并瀏覽網(wǎng)頁上各種各樣的信息.網(wǎng)頁開發(fā)者免費提供網(wǎng)頁信息給用戶，并通過互聯(lián)網(wǎng)廣告來獲得收益，用于網(wǎng)站的維護與更新，由此形成了一個良性的互聯(lián)網(wǎng)生態(tài)系統(tǒng).然而，惡意廣告的出現(xiàn)給用戶造成極大的困擾.這些惡意廣告跟蹤并竊取用戶的瀏覽信息[1,2]，造成隱私泄漏等威脅，嚴重影響用戶的訪問安全.因此，很多用戶選擇在瀏覽器上安裝廣告攔截器，用于屏蔽廣告，阻止惡意廣告的跟蹤和信息竊取[3].

AdBlock Plus1是目前最具代表性的廣告攔截器，它通過對網(wǎng)頁代碼與過濾列表easyList2進行正則表達式的匹配，從而識別并攔截廣告.這種方法能識別出大多數(shù)的廣告，效率較高，因而深受用戶歡迎.但這種方法也有一些缺點：

1)當網(wǎng)絡中出現(xiàn)新的廣告時，AdBlock Plus不能及時對廣告進行屏蔽，因為新出現(xiàn)廣告的URL地址尚未出現(xiàn)在過濾列表中，而AdBlock Plus需要人工不間斷地維護更新過濾列表.

2)除了對廣告JavaScript文件的匹配與攔截，AdBlock Plus還通過HTML元素的匹配來確定某個頁面元素是否是廣告，這可能會導致過濾廣告后的頁面出現(xiàn)大塊空白、排版錯亂等問題.

為了解決現(xiàn)有廣告過濾器的不足，減少人工維護列表所帶來的開銷并提高過濾精度，本文提出了一種結(jié)合靜態(tài)分析和特征識別的方法，來識別并屏蔽廣告.具體過程包括：首先，在搜集的數(shù)據(jù)集上，統(tǒng)計過濾列表并進行特征的提取，然后將提取到的特征放入分類器進行訓練，從而得到廣告分類模型，最后實現(xiàn)一個Chrome瀏覽器插件TriFilter，用于準確識別并屏蔽廣告.通過對546個網(wǎng)頁進行實驗，本文提出的方法能達到較好的精度(69.9%)和查準率(74%).

本文第二節(jié)介紹相關(guān)工作，包括廣告過濾器、反廣告過濾器和JS程序分析的研究現(xiàn)狀；第三節(jié)展示了論文的主要方法，包括對JS文件進行代碼解析、確定過濾列表和廣告特征、分類器的訓練以及瀏覽器插件的實現(xiàn)；第四節(jié)主要介紹本文的實驗部分，提出2個研究問題來考察TriFilter的有效性，并得到相應實驗結(jié)果；第五節(jié)對全文進行總結(jié)與展望.

2 相關(guān)工作

2.1 廣告過濾器

現(xiàn)有的廣告過濾器包括Adblock Plus、Adguard3、ADSafe4、保護傘廣告過濾器、廣告攔截大師5等.這些過濾器能夠過濾一些已知的廣告，但也存在一些問題，比如并未能真正實現(xiàn)準確有效的代碼識別并完全過濾廣告，或者錯誤地把普通網(wǎng)頁代碼理解為廣告代碼而進行刪除或屏蔽.例如，AdBlock Plus通過一個過濾列表來進行正則表達式的匹配(類似黑名單)，過濾列表中包括URL、元素ID以及一些域名等已經(jīng)確認是廣告的列表.但是對于一些新出現(xiàn)的廣告，則需要人工進行添加名單，否則不能識別出這類廣告，這類方法需要長期人工維護過濾列表，代價很大.

Orr C.R.[4]等人提出基于靜態(tài)分析方法來確定網(wǎng)頁中的廣告特征，從而區(qū)分廣告和正常的內(nèi)容.這些特征是通過對JS程序進行靜態(tài)分析得到的.在此基礎上，再使用SVM進行分類，以識別廣告JS文件.但是這種方法在確定特征的時候沒有進行實證研究，所選取的特征并不一定全部適用于現(xiàn)有的網(wǎng)頁情況；另外這篇論文并沒有通過插件實現(xiàn)可用的廣告過濾器.

另外也有研究通過程序分析和機器學習結(jié)合的方法[5,6]來對相關(guān)的JS文件進行識別，判斷是否是廣告文件，但在方法的精度和效率上還需要改善.

2.2 反廣告過濾器

如果越來越多的用戶使用廣告過濾器，會導致Web生態(tài)系統(tǒng)的失衡，造成巨大的影響.因此出現(xiàn)了一些方法用來阻攔AdBlocker的使用，例如，方法Antiblock6通過JavaScript來檢測用戶當前環(huán)境是否存在廣告屏蔽工具，如果存在這類工具，則要求用戶關(guān)閉AdBlocker或者對該網(wǎng)站內(nèi)容進行付費觀看，但是這種方法會降低用戶的使用體驗，因此Weihang Wang[7]等人提出了WebRanz工具，通過使用內(nèi)容和URL隨

機化方法來規(guī)避廣告過濾器.通過使用WebRanz，網(wǎng)頁發(fā)布者可以改變網(wǎng)頁元素的ID內(nèi)容，包括HTML、CSS和JavaScript等，使得廣告過濾器不能按照過濾列表來識別廣告.WebRanz重寫了原生JavaScript API，使得動態(tài)生成的DOM對象也能被隨機化，并且在不改變頁面功能和顯示效果的前提下使得廣告過濾器失效.

在實際應用中，出于安全保密或者存儲的需要，網(wǎng)頁中的JavaScript代碼和HTML代碼有時會被混淆或壓縮：原先具有明確語義的代碼變成一些肉眼難以識別和理解的字符串，但仍然可用一些專門的函數(shù)來解析，不影響輸出結(jié)果.另一方面，混淆技術(shù)[8,9]在現(xiàn)實中收集到的惡意腳本樣本中被大量采用，以逃避檢測.因此，一些網(wǎng)頁開發(fā)者在插入廣告時將廣告對應的ID以及URL做代碼混淆，這樣使得傳統(tǒng)的廣告過濾器也無法識別出廣告.

2.3 JS程序分析

JavaScript具有語法靈活性和高度動態(tài)性，易于使用，但代碼的可維護性不夠好.由于HTML元素和JavaScript代碼之間通過瀏覽器相互作用，進一步加劇了客戶端JavaScript代碼的維護問題.

目前，JS的程序分析分為靜態(tài)分析和動態(tài)分析兩種.通過對JS程序進行分析可以得到JS程序的相關(guān)信息并了解JS程序的功能.

在靜態(tài)分析方面，現(xiàn)有技術(shù)[10]大都需要對程序進行代碼解析、控制流圖和數(shù)據(jù)流圖構(gòu)建等工作，類似JS-WALA7這樣的分析框架(SAFE8，TAJS9等)提供了傳統(tǒng)的靜態(tài)分析器，但可擴展性不好，而且現(xiàn)有的 JavaScript的動態(tài)特性(比如JavaScript的原型鏈特性以及閉包特性等)使得靜態(tài)的程序流分析難以實施，無法獲得精確的分析結(jié)果；除此以外，大多數(shù)的JavaScript應用依賴于大的和復雜的庫和框架，與JavaScript原生代碼交織在一起，更增加了分析的難度[11].因此，長期以來，分析JavaScript程序被認為是一個巨大的挑戰(zhàn).

在動態(tài)分析方面，目前常用的分析工具有Jalangi[12]，支持影子執(zhí)行(shadow execution) 機制，在程序動態(tài)執(zhí)行過程中替換原本程序語句執(zhí)行的語義，并在執(zhí)行過程中通過更新影子值(shadow value) 來對原程序進行動態(tài)分析.通過該工具可以實現(xiàn)JS動態(tài)分析，如論文[13-15]都是在Jalangi框架上對JS代碼進行動態(tài)插樁分析并得到相應的運行時信息.

3 網(wǎng)頁廣告識別、過濾方法

3.1 方法概覽

本文給出一種基于程序分析與特征識別相結(jié)合的方法過濾網(wǎng)頁廣告，本文實現(xiàn)的廣告過濾插件的框架如圖1所示.

為了實現(xiàn)相應的插件，我們首先對捕獲到的網(wǎng)頁的JS文件進行代碼解析、生成AST樹，然后遍歷AST樹并提取出JS

文件的特征向量(3.2節(jié))；其次通過實證分析，確定哪些特征能作為區(qū)分廣告代碼與普通代碼的依據(jù)，并確定了一些常用的廣告JS文件，得到一個JS文件過濾表(3.3節(jié))；通過訓練好的分類器模型對得到的特征向量進行分類(3.4節(jié))，判斷文件是否是廣告JS文件，進而完成廣告過濾插件的實現(xiàn)(3.5節(jié)).

圖1 TriFilter結(jié)構(gòu)圖Fig.1 Structure of TriFilter

3.2 解析JS代碼

抽象語法樹(AST樹)是指源代碼語法所對應的樹狀結(jié)構(gòu).可以通過構(gòu)建語法樹將源代碼中的語句映射到樹上的每一個節(jié)點.通過遍歷，可以操縱語法樹并精確獲得程序代碼中的某個節(jié)點.

我們通過現(xiàn)有的語法解析器Esprima10將JavaScript代碼解析成一個用JSON文件表示的樹狀結(jié)構(gòu)并保存下來，文件中的結(jié)構(gòu)就是解析后的AST.通過遍歷抽象語法樹提取特征，將提取到的特征拼接成特征向量，這樣就可以得到每個JavaScript文件對應的特征向量.

3.3 確定過濾列表和廣告特征

為了確定區(qū)別廣告代碼和其它JS代碼的特征，我們首先進行了實證分析，在現(xiàn)有論文基礎上對提取的一些特征進行研究，分析哪些特征能對廣告文件和非廣告文件的區(qū)分起到更好的效果；然后給出具體的特征表示.

3.3.1 實證分析

論文[4]將廣告代碼特征分為7大類，分別是混淆代碼(Code obfuscation)、動態(tài)代碼和URL生成(Dynamic code and URL generation)、代碼結(jié)構(gòu)(Code Structure)、函數(shù)調(diào)用分布(Function call distribution)、事件處理(Event handling)、腳本源(Script origin)、關(guān)鍵詞的存在(Presence of keywords)以及一些不屬于這些類別的特征，如ad字樣.在此基礎上，本文進行實證分析，以確定廣告特征.

為了確定有用的特征，我們在216個網(wǎng)頁上對論文[4]中的特征進行統(tǒng)計，由于統(tǒng)計后大部分特征在廣告和非廣告的JS文件中都大量出現(xiàn)，我們刪除了那些在廣告文件中從未出現(xiàn)過或極少出現(xiàn)的特征，其中包括混淆代碼.對于一個特征是否加入廣告或非廣告特征，我們根據(jù)這一特征在廣告文件中出現(xiàn)的次數(shù)是否大于在非廣告文件中出現(xiàn)次數(shù)的1.5倍進行判斷.

3.3.2 特征表示

通過實證研究，我們確定了4個類別總計21個特征來表示廣告特征向量.這四個類別分別是代碼結(jié)構(gòu)、函數(shù)調(diào)用分布、事件處理以及其它(包含ad字樣).每個類別中包含的特

征如表1所示.

3.4 訓練分類器

本文采用對數(shù)幾率回歸算法以及十折交叉驗證來實現(xiàn)一個二分類分類器.十折交叉驗證將數(shù)據(jù)集分成十份，輪流將其中的1份作為測試集，9份作為訓練數(shù)據(jù)，10次的結(jié)果的正確率(或差錯率)的平均值作為對算法精度的估計.每一次的訓練算法采用的是對數(shù)幾率回歸，也即Logistic Regression(LR).

LR可以看作泛化的線性模型，其訓練的主要工作是對于我們提取出的特征向量賦權(quán)值.一個網(wǎng)頁的某個特征向量在決定該網(wǎng)頁是否為廣告時所起的作用越大，其所占的比重越高.當一個LR模型訓練出來后，對于新來的網(wǎng)頁，我們依舊提取其特征向量，并使用我們訓練出來的各向量權(quán)重beta進行計算，從而判別出分類結(jié)果.

表1 特征分類及表示Table1 Classification and representation of features

由此可見：在對數(shù)幾率回歸中，我們主要通過訓練過程不斷調(diào)整權(quán)重向量參數(shù)beta.對于給定的數(shù)據(jù)集，對率回歸模型最大化“對數(shù)似然”(log-likelihood)：

(1)

我們使用牛頓法或梯度下降法求解beta參數(shù)，通過調(diào)整學習率、訓練輪數(shù)等參數(shù)，對模型進行微調(diào)，通過加大訓練集、調(diào)整特征向量，對精度做進一步提升.

當權(quán)重向量beta參數(shù)求解出來后，對于一個待檢測的新網(wǎng)頁，我們使用3.3節(jié)中方法提取出該網(wǎng)頁JS文件的特征向量后，使用算法1判斷該網(wǎng)頁是否廣告相關(guān).

Algorithm1. AdDetection

Input：BETA：Weight coefficient vector

PATH：Path of JavaScript files

Output：”ad” or ”other”.The result of the judgment

1：/*Stage 1-Build the AST of input file */

2：jsScript←fs.readFileSync(PATH，"utf-8")

3：ast←esprima.parse(jsScript)

4：/*Stage 2-Extract the eigenvector*/

5：recordTables←BFS(ast)

6：individualOut←compositeResult(recordTables)

7：individualNum←countResult(individualOut)

8：/*Stage 3-Calculate the result of the judgment*/

9：result←0

10：foreachb∈BETA，eachx∈individualNumdo

11： result←result-b·x

12：endfor

13：result←1/(Math.exp(result)+1)

14：ifresult>=0.5 then

15：returnad

16：else

17：returnother

上述算法中，第2～3行讀取待檢測網(wǎng)頁的JS文件，構(gòu)建該文件的AST；第5～7行使用BFS方法遍歷AST，提取表1中的特征向量，存入individualOut中，統(tǒng)計每個特征向量出現(xiàn)次數(shù)，存入individualNum中；第9～17行，使用訓練好的LR模型判斷該JS文件是否ad相關(guān)，輸出結(jié)果.

3.5 TriFilter三次過濾的實現(xiàn)

本文計劃實現(xiàn)的廣告過濾器是一個Chrome瀏覽器擴展插件，其實現(xiàn)過程包括三次過濾，故將其命名為TriFilter.

首先我們需要確定一個小規(guī)模的JS文件過濾表(主要包括百度、谷歌等常見推廣廣告的JS文件名與URL地址)和白名單表(已經(jīng)確認的不需要攔截的JS文件及URL，主要包括已審查過的非廣告類及位于白名單的列表)，通過在線加載的方式，在遍歷HTML頁面時，對與列表匹配的JS文件進行過濾，也即不加載匹配到的JS文件；

然后對加載后的JS文件內(nèi)容進行分析，將加載得到的JS文件進行靜態(tài)分析，得到對應的AST樹，然后提取特征并通過訓練好的分類器模型對JS文件分類，判斷是否是廣告JS文件，若是廣告JS文件，則實行“block”操作，讓瀏覽器不加載該JS文件；

另外，在得到分類器判斷結(jié)果后，Tri-blocker會自動將判斷的結(jié)果更新到第一步的文件過濾表和白名單；

最后，對得到的html文件再進行一次遍歷審查，對需要屏蔽的元素實行“display：none”操作.

3.6 插件TriFilter的算法優(yōu)化

使用簡單的LR分類器，我們的插件TriFilter能夠識別廣告網(wǎng)站和非廣告網(wǎng)站(具體實驗評估結(jié)果詳見第4節(jié))，但仍然存在精確率不足，尤其是召回率較低的問題.出現(xiàn)這樣的問題，主要是由于以下兩點：

1)廣告代碼特征提取較為困難.一段含有廣告的源代碼，往往與普通代碼結(jié)構(gòu)十分相似，有可能被誤認為非廣告代碼.只有通過大量的數(shù)據(jù)收集，才能正確總結(jié)出代碼特征，并將之運用到訓練器中，不斷調(diào)整參數(shù)、訓練結(jié)果.為此，我們需要進一步擴大訓練集從而進行優(yōu)化.

2)我們采取的對數(shù)邏輯回歸模型是適用于二分類的訓練模型，但在實踐中面對現(xiàn)實網(wǎng)頁源代碼錯綜復雜、看似毫無規(guī)律的特征數(shù)據(jù)時，有可能精度方面有所限制.為此，我們擬采用集成學習的方法進行解決.

集成學習(ensemble learning)通過構(gòu)建并結(jié)合多個學習器來完成學習任務，這些個體學習器可以是同一種學習器，也可以是不同種學習器.集成學習通過將多個學習器進行結(jié)合，常會獲得比單一學習器顯著卓越的泛化性能.我們擬采用AdaBoost族算法，基于最簡單的“加性模式”進行求解.

(2)

其工作機制主要為：先從初始訓練集訓練出基學習器LR，再根據(jù)基學習器的表現(xiàn)對訓練樣本分布進行調(diào)整，使先前學習器做錯的訓練樣本在后續(xù)收到更多關(guān)注，然后基于調(diào)整后的樣本分布訓練下一個基學習器.

其中，我們令每個弱分類器的組成是 [閾值 偏置 特征列]，使用基學習器的[errorRate TPRate FPRate]評價其表現(xiàn)，規(guī)定訓練停止的條件為：達到預設定訓練輪數(shù)或基學習器錯誤率小于某個數(shù).

使用集成學習器，能夠進一步提高我們工具的廣告識別精度，其實驗評估結(jié)果(LRBoost)詳見第4節(jié).

4 實驗評估

本實驗在Windows系統(tǒng)下進行，采用JavaScript語言實現(xiàn)Chrome插件，IDE采用JetBrains WebStorm 10.0.1，數(shù)據(jù)集來源為互聯(lián)網(wǎng)各大網(wǎng)站網(wǎng)頁源碼.

為了驗證本文提出的方法的有效性，我們提出下面兩個研究問題：

RQ1：和論文[4]相比較，我們得到的新特征列表是否有效？與簡單使用LR的方法相比，我們提出的集成學習改進策略是否有效？

RQ2：本文提出的方法是否能夠有效識別廣告？對于研究問題1，本文分別對論文[4]的方法和本文的兩種方法進行實驗，通過對數(shù)據(jù)集(包含546個網(wǎng)站，其中JS文件有214個，非JS文件有332個)進行訓練，對兩者的實驗結(jié)果進行比較，具體結(jié)果見表2.其中，

TP(True Positive)，TN(True Negative)，F(xiàn)P(False Positive)，F(xiàn)N(False Negative)分別表示被識別為廣告的廣告、被識別為非廣告的非廣告、被識別為非廣告的廣告、被識別為廣告的非廣告.

表2 論文[4]、TriFilter、LRBoost方法的比較結(jié)果Table 2 Comparison results of three methods

由表2可知，與論文[4]中方法相比，我們的方法具有更高的精度(提升18%)、查準率(提升18%)和查全率(提升120%)，特別體現(xiàn)在查全率的提升上，說明我們方法所選取的特征更能有效區(qū)分出廣告與非廣告.

另外，我們比較了簡單分類器和集成學習的實驗結(jié)果，發(fā)現(xiàn)LRBoost方法在精度上有1.7%的提升，在查準率上有20%的提升，但在查全率上略有下降(9.6%).一般情況下，查全率和查準率會互相牽制，原因在于：當查準率較高時，通常廣告網(wǎng)頁的比例會比較高，但難免會漏掉一些廣告網(wǎng)頁，導致查全率較低；但當查全率較高時，通常廣告相關(guān)的網(wǎng)頁比較多，但不可避免地有非廣告網(wǎng)頁被誤判為廣告相關(guān)，導致查準率較低.因此，應該結(jié)合要處理的問題決定查準率和查全率的權(quán)衡.在過濾網(wǎng)站廣告的實例中，我們認為：誤將普通網(wǎng)頁判定為廣告網(wǎng)頁的嚴重程度高于漏報廣告網(wǎng)頁的嚴重程度，因此，我們更傾向于查準率的提高.

對于研究問題2，我們隨機選取了20個非訓練集中的網(wǎng)站進行實驗，使用TriFilter對這些網(wǎng)站上的廣告進行識別，并計算正確識別的廣告?zhèn)€數(shù)以及誤報的個數(shù)(基準通過人工審查來確定)，然后計算精度、查準率和查全率.實驗結(jié)果如表3所示，我們使用TriFilter識別這20個網(wǎng)站上的廣告及非廣告文件.其中第一列表示網(wǎng)站的名稱，第二列、第三列分別表示網(wǎng)站中的廣告文件數(shù)和非廣告文件數(shù)(由人工審查確定)，TP表示識別出的廣告文件數(shù)，TN表示識別出的非廣告文件數(shù)，F(xiàn)P表示未識別出的廣告文件數(shù)，F(xiàn)N表示未識別出的非廣告文件數(shù).

表3 TriFilter的廣告識別結(jié)果Table 3 Results of TriFilter

從實驗結(jié)果來看，對于這20個非訓練集數(shù)據(jù)，我們的插件TriFilter能達到62.5%的精度、70.1%的查準率和40.9%的查全率.在該數(shù)據(jù)集上的精度和查全率和分類器的準確率相比略有降低，但是查準率有明顯的提高，因此我們的分類器對于未曾訓練的廣告的識別具有較好的效果，這說明我們選取的特征可以較為準確地識別出web廣告.

5 總結(jié)與展望

本文通過靜態(tài)分析的方法對JS代碼提取特征，并結(jié)合機器學習的方法進行訓練學習，通過訓練得到一個可用于識別廣告的分類器模型；然后根據(jù)Chrome瀏覽器插件的規(guī)則實現(xiàn)了廣告過濾器TriFilter.區(qū)別于現(xiàn)有廣告過濾器需要維護龐大的黑名單列表，我們的TriFilter能自動識別頁面廣告代碼并在最終展示時過濾掉頁面上的廣告.

實驗結(jié)果說明了我們方法的有效性，但還需要進一步提高精度、查準率和查全率，尤其是查全率，我們可以考慮對廣告代碼的特征提取步驟進行優(yōu)化，可以通過進一步擴大實驗數(shù)據(jù)和增加特征來完善.