基于概率模型的電子秤作弊序列碼預(yù)測方法

張 娟，陳 浩

（1.西安計(jì)量技術(shù)研究院，陜西 西安 710068；2.西安理工大學(xué)，陜西 西安 710048）

0 引 言

電子秤又稱為數(shù)字指示秤，是一種廣泛應(yīng)用于商場、批發(fā)市場和農(nóng)貿(mào)市場中的計(jì)量儀器，少數(shù)商販?zhǔn)褂脦в凶鞅仔酒碾娮映?，通過按鍵組合形成作弊序列碼（Cheat Sequence Code，CSC），使電子秤進(jìn)入作弊模式，從而實(shí)現(xiàn)更改重量顯示，達(dá)到作弊計(jì)量的目的。這種作弊電子秤的存在，嚴(yán)重?fù)p害了消費(fèi)者的權(quán)益。作弊電子秤的正確檢測對維護(hù)市場公正具有重要的積極意義[1]。目前，針對通過作弊序列碼方式激活作弊模式的電子秤，主要的檢測手段是通過嘗試輸入預(yù)測的作弊序列碼，并檢查電子秤的作弊模式是否被激活來檢測電子秤是否具有作弊功能。其實(shí)，作弊序列碼的預(yù)測在本質(zhì)上與密碼破解相類似，但因其使用領(lǐng)域和“密碼”組合類型的特殊性，使得常用的密碼破解技術(shù)在該待研究問題上的效果并不顯著。

對于輸入的作弊序列碼，目前最常用的方法是窮舉法[2?3]，這種方法根據(jù)電子秤上數(shù)字鍵盤的按鍵數(shù)量與類型，通過排列組合的方式生成預(yù)測作弊序列碼，再逐個(gè)輸入電子秤進(jìn)行有效性檢測。這種方式的檢測效率取決于作弊序列碼的復(fù)雜程度和輸入順序，存在較大的偶然性，準(zhǔn)確率與覆蓋率極低。窮舉法屬于暴利破解，由于巨大的嘗試量而導(dǎo)致無法在規(guī)定的時(shí)間內(nèi)成功獲得正確的結(jié)果。另外一種方法叫做字典法，其更貼合人類創(chuàng)建各種口令、密碼時(shí)的規(guī)律[4]。但選擇合適高效的密碼字典在基于字典的密碼破解中是比較困難的，再加上不同的領(lǐng)域或方向所設(shè)置密碼的習(xí)慣不盡相同，這就使選擇合適的字典難度更大。因此要想提高字典法的效率，需要根據(jù)該電子秤以及作弊序列碼的特點(diǎn)生成專用的密碼字典[5]來進(jìn)行作弊碼的預(yù)測。

因獲取真實(shí)的大規(guī)模作弊碼對研究人員來說非常困難，故本文利用機(jī)器學(xué)習(xí)領(lǐng)域虛擬樣本生成的思想，提出了一種利用已收集到的作弊碼作為小樣本來生成能夠高效命中待檢測電子秤中作弊碼的預(yù)測集的方法。在機(jī)器學(xué)習(xí)領(lǐng)域，虛擬樣本是指在未知樣本概率分布函數(shù)的情況下，利用研究領(lǐng)域先驗(yàn)知識并結(jié)合已有的訓(xùn)練樣本，產(chǎn)生待研究問題的樣本空間中的部分合理樣本[6?9]。在作弊碼預(yù)測集生成的問題中，先驗(yàn)知識表現(xiàn)為現(xiàn)有的作弊碼中發(fā)現(xiàn)的某些作弊序列碼的設(shè)置規(guī)律，作弊碼預(yù)測集的目標(biāo)是盡可能地生成屬于真實(shí)作弊碼分布空間的樣本，即預(yù)測集中盡可能高效地命中作弊碼。

基于這一思想，本文通過分析作弊序列碼的有限樣本集的結(jié)構(gòu)獲得作弊序列碼結(jié)構(gòu)模板，建立作弊序列碼的概率模型，生成作弊序列碼預(yù)測集，以提高作弊序列碼檢測集的質(zhì)量和效率。

1 相關(guān)工作

由于收集到的作弊序列碼有限，因此本文采用了口令生成的方法來命中電子秤的作弊序列碼。目前，口令生成的方法大致分為三類：

1）基于特定場景的規(guī)則產(chǎn)生一定特征的口令；

2）基于字典，再結(jié)合一些變形的規(guī)則產(chǎn)生新的口令；

3）基于口令的概率模型，訓(xùn)練數(shù)據(jù)，并產(chǎn)生模型空間中的其他口令。

其中，基于概率模型[10?11]的方法相對于其他的方法具有更好的適應(yīng)性和擴(kuò)展性。利用概率模型生成“口令”的過程大致包括訓(xùn)練樣本數(shù)據(jù)、建立概率模型以及再生成概率空間中可能包含的其他口令?？诹钅Ｐ鸵话阌址譃榛谡麄€(gè)字符串的以及基于模板的模型。因電子秤的字符類型劃分比較明確，所以本文選用基于模板的概率模型。

但該基于概率模型的方法并不能完整地描述小樣本中包含的分布信息。同時(shí)，鑒于作弊碼的字符組成類型較特殊，不同于常見的口令密碼，對該問題的先驗(yàn)知識不是很明顯。因此，為了保證作弊序列碼檢測的效率和命中率，本文在使用概率模型的基礎(chǔ)上，結(jié)合一定的變形規(guī)則，采用基于擾動(dòng)的方式[12?13]生成作弊序列碼的預(yù)測集。

2 作弊序列碼結(jié)構(gòu)

目前，電子秤基于按鍵組合形成的作弊序列碼主要由電子秤鍵盤上的三種字符類型組成，即數(shù)字鍵（D）、功能鍵（F）和存儲(chǔ)鍵（M）。數(shù)字鍵主要包含鍵盤上的數(shù)字按鍵區(qū)域，取值范圍為0～9。功能鍵主要包括“去皮”“置零”“累加”“記憶”等按鍵。存儲(chǔ)鍵主要由多個(gè)用于存儲(chǔ)數(shù)字的按鍵組成，一般表示為M1～M9。作弊序列碼中，數(shù)字鍵的使用次數(shù)最多，其次是功能鍵，存儲(chǔ)鍵使用頻率最小。作弊序列碼的組合字符不具有具體的語義信息，偏向以上述三種按鍵字符的隨機(jī)組合，整體呈分段式，段與段之間相互獨(dú)立，每個(gè)段為連續(xù)相同類型的字符。作弊序列碼一般以數(shù)字鍵開始，功能鍵或者存儲(chǔ)鍵結(jié)尾。

設(shè)有作弊序列碼d1d2d3f1f2m1，其中d1，d2，d3為具體的數(shù)字鍵值，f1，f2為功能鍵值，m1為存儲(chǔ)鍵值，其含有3 位數(shù)字鍵、2 位功能鍵和1 位存儲(chǔ)鍵，對應(yīng)的結(jié)構(gòu)為D3F2M1，這種按順序表示的符號結(jié)構(gòu)組成方式就是其結(jié)構(gòu)，也稱為模板。則對于任意作弊序列碼c，其模板如下：

式中：λ，φ，ω分別為作弊序列碼集C中三段D，F(xiàn)，M的長度，即數(shù)字鍵、功能鍵和存儲(chǔ)鍵的數(shù)量。存儲(chǔ)鍵M為可選，則c可通過模板t（c）對應(yīng)的規(guī)則生成。那么對于作弊序列碼樣本集C，其有對應(yīng)的模板集T，可由T所定義的結(jié)構(gòu)生成C。若c∈C，則t（c）∈T。

電子秤作弊序列碼通常為了方便記憶，其長度短，相似度高，且由于電子秤的按鍵數(shù)量較少，作弊序列碼必須要以不影響正常的按鍵邏輯為前提。由于電子秤按鍵的特殊性，因此其可用的按鍵范圍有限。

基于以上對作弊序列碼的結(jié)構(gòu)特征分析，本文通過建立作弊序列碼及其模板的概率模型，基于虛擬樣本生成技術(shù)設(shè)計(jì)作弊序列碼變形規(guī)則，實(shí)現(xiàn)擴(kuò)充現(xiàn)有作弊序列碼集，生成作弊序列碼預(yù)測集，提高作弊序列碼檢測的覆蓋率和準(zhǔn)確率。

3 作弊序列碼的概率模型

為了建立有效的作弊序列碼預(yù)測集，提高其在原始作弊序列碼集中的覆蓋率，需要生成的作弊序列碼集中在概率空間的高概率部分，因此，需對生成的作弊序列碼進(jìn)行概率計(jì)算[14?18]。

作弊序列碼樣本集C中的元素c的概率模型表示如下：

式中：d1，d2，…，dλ為具體的數(shù)字鍵值；f1，f2，…，fφ為功能鍵值；m1，m2，…，mω為存儲(chǔ)鍵值；P（DλFφMω）為模板t（c）的概率；P((d1d2…dλ)|Dλ)指使用d1d2…dλ實(shí)例化Dλ的概率，即長度為λ的數(shù)字鍵字符串出現(xiàn)的頻率；P((f1f2…fφ)|Fφ)指長度為φ的功能鍵字符串的概率；P((m1m2…mω)|Mω)指長度為ω的存儲(chǔ)鍵字符串的概率。

為了進(jìn)一步計(jì)算一個(gè)生成的作弊序列碼的概率，這里需要計(jì)算模板t（c）以及其字符段d1d2…dλ，f1f2…fφ，m1m2…mω的分配概率。需對作弊序列碼樣本集C對應(yīng)的模板集T進(jìn)行預(yù)處理，根據(jù)字符類型分離出每個(gè)子模板t（c）對應(yīng)的字符串集合片段，并為模板以及具體的字符串片段分配概率。

對于模板集T的任意模板t（c），其根據(jù)數(shù)字、功能、存儲(chǔ)鍵字符類型可劃分為字符段Dλ，F(xiàn)φ和Mω，則有模板t（c）的字符段集合S（c），Dλ，F(xiàn)φ和Mω∈S（c）。那么可得模板集T中的所有模板的字符段S1，S2，…Sn，n∈R組成了集合STR，S1，S2，…，Sn∈STR?；谝陨锨闆r，這里給出以下定義：

定義1：模板t所對應(yīng)的作弊序列碼的數(shù)量與模板集T中所有模板對應(yīng)的作弊序列碼數(shù)量之比，稱為模板t的概率。

定義2：字符段s在字符段集合Si中的數(shù)量與Si的所有字符段數(shù)量之比，稱為字符段s的概率，其中s∈Si，1≤i≤n，Si∈STR。

令計(jì)數(shù)函數(shù)為count，概率由函數(shù)p給出，根據(jù)定義1 和定義2 可知，集合T和Si滿足：

那么，模板t以及字符串s的概率為：

式中：p（t）表示模板t的概率；count（t）代表t所對應(yīng)的作弊序列碼的數(shù)量；count（T）代表T所對應(yīng)的作弊序列碼的數(shù)量；p（s）為字符串s的概率；count（s）為s在字符段集合Si中的數(shù)量；count（Si）為Si所有字符段數(shù)量。

4 作弊序列碼預(yù)測集的生成

為了對電子秤的作弊序列碼進(jìn)行預(yù)測，本文基于作弊序列碼樣本集C，結(jié)合作弊序列碼的概率模型p，通過作弊序列碼的模板集對樣本空間進(jìn)行擴(kuò)充，獲得虛擬樣本，即作弊序列碼預(yù)測集SIM，以提高對未知電子秤作弊序列碼預(yù)測的準(zhǔn)確性。作弊序列碼預(yù)測集的生成過程如圖1所示。

圖1 作弊序列碼預(yù)測集的生成流程

設(shè)作弊序列碼預(yù)測集SIM 容量為N，其基于作弊序列碼樣本集C的模板集T生成，樣本集C容量為U，模板集T的元素個(gè)數(shù)為k，k≤U。令，X為根據(jù)樣本集C的每一個(gè)元素生成的預(yù)測作弊序列碼個(gè)數(shù)。

根據(jù)預(yù)測作弊序列碼生成的三種情況，有以下生成過程：

1）將作弊序列碼樣本集中的作弊序列碼c1，c2，…，cu∈C形成作弊序列碼預(yù)測集合sim1，加入預(yù)測集SIM，令c1，c2，…，cu∈SIM，生成的作弊序列碼數(shù)量為N1=u。

2）遍歷作弊序列碼樣本集C的元素c，獲得其對應(yīng)的t（c）∈T，在字符段集合STR 中搜索集合其對應(yīng)的字符段集合S1，S2，…，Si，其中1≤i≤n，根據(jù)t（c）的模板結(jié)構(gòu)，分別在D，F(xiàn)，M類型的片段所屬的字符段子集隨機(jī)選擇字符串段Dα，F(xiàn)β，Mγ，其中1≤α，β，γ≤n），Dα，F(xiàn)β，Mγ∈S組成作弊序列碼y，同時(shí)計(jì)算概率p（y），若p（y）<1N，則重新選擇字符段生成作弊序列碼y。若生成的y的概率p（y）<1N的次數(shù)count 大于閾值num，則基于字符段的變形規(guī)則Transform 方法重新生成y，最終獲得預(yù)測作弊序列碼集合sim2，sim2?SIM。重復(fù)此過程X-1 次，獲得生成作弊序列碼數(shù)量為N2=（X-1）u。

3）由于N不一定是U的整數(shù)倍，因此，需對剩余數(shù)量的預(yù)測作弊序列碼進(jìn)行填補(bǔ)，其數(shù)量為N3=N-X·u。在作弊序列碼樣本集C中隨機(jī)選擇X1條樣本形成樣本集，其中X1=N3X，繼續(xù)使用過程2）中的方法生成作弊序列碼，獲得集合sim3，sim3?SIM。最終得到完整的作弊序列碼預(yù)測集SIM。

經(jīng)過以上方法獲得作弊序列碼預(yù)測集SIM，可對具有作弊性的電子秤進(jìn)行作弊碼檢測，快速判斷電子秤的作弊性。

5 Transform 方法

Transform 方法主要是基于以下規(guī)則對作弊序列碼集C進(jìn)行變形得到預(yù)測作弊序列碼集合Y，從而完成SIM 的構(gòu)造。不同的變形規(guī)則對結(jié)果會(huì)造成不同影響[19?20]，本文對作弊序列碼C的變形規(guī)則定義為刪除、插入、交換三種操作，之后得到Y(jié)，再將其加入SIM。下面將詳細(xì)描述三類變形規(guī)則。

5.1 規(guī)則1：刪除

刪除規(guī)則主要針對作弊序列碼中的存儲(chǔ)鍵、重復(fù)字段和重復(fù)字符進(jìn)行刪除操作。

1）刪除存儲(chǔ)鍵字段。對于作弊序列碼c，若其模板t（c）中有存儲(chǔ)鍵（M）字段，則將整段存儲(chǔ)鍵（M）字段刪除。即若作弊序列碼c=d1d2d3f1f2m1，其模板t（c）=D3F2M1，刪除存儲(chǔ)m1后得到作弊預(yù)測碼y=d1d2d3f1f2。

2）刪除重復(fù)字符。對于作弊序列碼c，若其存在重復(fù)字符，則刪除其中重復(fù)出現(xiàn)的字符。即若作弊序列碼c=d1d2d1d1f1f2，模板t（c）=D4F2，刪除其中重復(fù)出現(xiàn)的d1字符，刪除后得到y(tǒng)=d1d2f1f2。

3）刪除重復(fù)字段。對于作弊序列碼c，若其存在重復(fù)字段，則刪除其中重復(fù)出現(xiàn)的字段。即若作弊序列碼c=d1d2d3f1f2d1d2d3，模板t（c）=D3F2D3，刪除其中重復(fù)出現(xiàn)的D3字段，刪除后得到y(tǒng)=d1d2d3f1f2。

5.2 規(guī)則2：插入

根據(jù)對作弊序列碼樣本集C的結(jié)構(gòu)可知，數(shù)字鍵（D）的使用率較高，且多數(shù)集中在1～5 位。因此，該規(guī)則選擇在D1或D2所對應(yīng)的子集Si中隨機(jī)選擇字符串s插入到C中數(shù)字段的頭部或尾部。即若作弊序列碼c的模板t（c）=DiFjMk，然后在D1或D2所對應(yīng)的子集Si中隨機(jī)選取字符串Dq，q>0，將其插入到數(shù)字段的頭部或尾部，得到模板為t（y）=DnFjMk（n=i+k）的作弊預(yù)測碼y。

5.3 規(guī)則3：交換

該規(guī)則是按照順序依次判斷滿足條件，進(jìn)而對作弊序列碼c進(jìn)行變形得到y(tǒng)。

1）段內(nèi)隨機(jī)排序。對于作弊序列碼c模板t（c）=DiFjMk，i，j，k分別代表每個(gè)段的長度，若其中存在長度大于3 的段，即i≥3 或j≥3 或k≥3，則對該段的段內(nèi)字符進(jìn)行隨機(jī)排序，排序結(jié)果由隨機(jī)函數(shù)所決定，但t（c）仍保持不變。

2）字符段逆序排列。將整個(gè)作弊序列碼c按照字符類型進(jìn)行逆序排序，得到作弊預(yù)測碼y，即段內(nèi)字符逆序排列輸出。即作弊序列碼c=d1d2d3d4f1f2，字符段逆序排列后得到y(tǒng)=d4d3d2d1f2f1。

6 實(shí)驗(yàn)結(jié)果和分析

為了進(jìn)一步驗(yàn)證以上方法的有效性，實(shí)驗(yàn)基于計(jì)量執(zhí)法過程中收繳的電子秤的作弊序列碼樣本建立作弊序列碼預(yù)測集。

通過上述方法生成的作弊序列碼預(yù)測集具有較高的真實(shí)性，并保持著樣本集中作弊序列碼的結(jié)構(gòu)分布規(guī)律。實(shí)驗(yàn)從作弊電子秤的作弊序列碼的命中率和運(yùn)行耗時(shí)兩方面測試該方法的有效性。命中率（Rate）指作弊序列碼預(yù)測集在原始數(shù)據(jù)集中命中的作弊碼所占的比例，這體現(xiàn)了該算法生成的預(yù)測集對原始數(shù)據(jù)集的還原能力。運(yùn)行耗時(shí)（Time）指針對一定規(guī)模的電子秤進(jìn)行作弊序列碼測試，即用基于樣本生成的預(yù)測集去與電子秤進(jìn)行碰撞，觀察能否將電子秤的作弊序列碼預(yù)測成功，若能，則統(tǒng)計(jì)預(yù)測這些電子秤作弊碼所需要的時(shí)間。

實(shí)驗(yàn)的主要流程如下：

1）依照作弊序列碼的結(jié)構(gòu)特點(diǎn)，隨機(jī)生成規(guī)模為1 000 的原始數(shù)據(jù)集Q。按照DλFφMω的規(guī)則形式生成，1≤λ≤3，0≤φ≤1，0≤ω≤1。

2）在原始數(shù)據(jù)集Q中隨機(jī)分別抽取一部分樣本組成作弊序列碼樣本集C，樣本集C的規(guī)模分別為200，250，300，350，400，450，500。基于該作弊序列碼樣本集C，使用本文方法生成規(guī)模為樣本集C的5 倍的作弊序列碼預(yù)測集SIM。

3）在原始數(shù)據(jù)集Q中剩余的樣本中，依次隨機(jī)選擇10，15，20，25，30，35，40 條作弊序列碼樣本組成不同規(guī)模的測試集TS。用本次生成的預(yù)測集SIM 依次與不同規(guī)模的測試集TS 進(jìn)行碰撞，統(tǒng)計(jì)在不同規(guī)模的TS 中的命中率（Rate）以及命中作弊序列碼所需要的時(shí)間。在與某一規(guī)模TS 碰撞時(shí)，隨機(jī)在SIM 中選取作弊序列預(yù)測碼y去測試，選取后便不再放回。

實(shí)驗(yàn)的運(yùn)行環(huán)境為Windows 10 系統(tǒng)，CPU 為Intel i7?8550U，內(nèi)存大小為4.0 GB。

圖2為樣本集C的規(guī)模分別為200，250，300，350，400，450，500 情況下，測試對10，15，20，25，30，35，40 條作弊序列碼的命中率情況。

圖2 不同樣本規(guī)模下的命中率

由圖2可知，在不同的測試集下，其命中率均在50%左右，隨著測試集的增加，命中率相對穩(wěn)定?？梢姡疚牡念A(yù)測方法可在不同的測試樣本下保持穩(wěn)定的命中率。

為了進(jìn)一步說明本文方法的有效性，圖3展示了預(yù)測集在對10，15，20，25，30，35，40 條作弊序列碼的命中測試過程中的耗時(shí)情況。

由圖3可知，在10條測試作弊序列碼的耗時(shí)最短，耗時(shí)約0.025 ms；在40 條時(shí)，耗時(shí)最多，大約為0.035 ms。這表明隨著測試作弊序列碼的條數(shù)增加，耗時(shí)大約呈線性增加，這是由于測試過程中的對比次數(shù)相應(yīng)的增多。

圖3 不同測試樣本下的運(yùn)行耗時(shí)

為了能夠更加直觀地說明該方法的有效性，現(xiàn)將兩種評估指標(biāo)綜合進(jìn)行對比，如表1所示。

通過表1的數(shù)據(jù)分析可以看出，本文所提出的作弊序列碼預(yù)測方法作弊序列碼命中率穩(wěn)定，且耗時(shí)短，表明該方法具有一定的有效性。

表1 不同測試樣本下的平均命中率和平均耗時(shí)

7 結(jié) 論

作弊序列碼的生成過程實(shí)際上是兩個(gè)層次的概率組合，一層是作弊序列碼的模板結(jié)構(gòu)的概率組合，另一層是指示秤按鍵字符串的概率組合。

本文針對電子秤作弊性檢測過程中的作弊序列碼生成匹配問題，基于概率模型與虛擬樣本技術(shù)提出一種可行且有效的電子秤作弊序列碼生成方法。在接下來的研究工作中，本研究將對該方法的規(guī)則變化部分進(jìn)行深入研究與優(yōu)化。同時(shí)，該方法在樣本空間與命中率方面還有一定的改進(jìn)空間，可從作弊序列碼的變形方法與擴(kuò)大樣本和預(yù)測集空間的比例進(jìn)行進(jìn)一步的詳細(xì)研究，以提高電子秤作弊檢測的效率。