一個簡單的學生成績發(fā)布方法

易通，石民勇

(中國傳媒大學 計算機學院，北京 100024)

一個簡單的學生成績發(fā)布方法

易通，石民勇

(中國傳媒大學 計算機學院，北京 100024)

對學生學習成績的分析，能夠為教學模式的改進提供一些有價值的信息。分析學習成績的同時，學生的個人隱私也需要得到保護，這就需要一個安全有效的學生成績發(fā)布方法。本文在先前工作的基礎上，提出了一個簡單實用的學生成績發(fā)布方法，并驗證了它的安全性。

學習成績；隱私；安全；數(shù)據(jù)發(fā)布

1 引言

學生成績的管理是一項重要的工作，大量的學生成績中往往蘊藏著一些有價值的規(guī)律，通過挖掘和分析這些信息能夠為教學管理、教學決策等提供有效的指導。但是學生的成績往往會涉及到學生的個人隱私，例如不合格的考試成績，所以在對學生成績進行分析之前需要對成績表進行匿名處理，這也就涉及到了數(shù)據(jù)發(fā)布技術。

數(shù)據(jù)發(fā)布技術在保持信息可用性的同時，需要保證用戶的隱私安全。K-匿名[1-2]是一個典型的數(shù)據(jù)發(fā)布模型，它要求每個分組至少由K條記錄構成，且每個分組中的記錄經(jīng)過泛化后都具有相同的準標識符。也就是在發(fā)布的數(shù)據(jù)表中，對于每一條記錄，都無法把它從K條記錄中區(qū)分出來。但是K匿名模型沒有考慮到敏感屬性值多樣性的問題，容易受到同質(zhì)攻擊，因此也就有了L-多樣化模型[3]。L-多樣化模型要求每個分組中都至少有L個不同的敏感屬性值，從而保證了敏感值的多樣性?；贙-匿名和L-多樣化這兩個基本模型，后來一系列的數(shù)據(jù)發(fā)布模型[4-8]也被提出。

但是關于成績發(fā)布模型的研究仍然較少，文獻[9]直接把K-匿名模型用于學生成績的發(fā)布，我們之前的工作[10]已經(jīng)指出，由于學生成績自身的特點，多數(shù)現(xiàn)有的數(shù)據(jù)發(fā)布模型并不適用于學生成績的發(fā)布。通過分析，歸納了學生成績發(fā)布的一些特點[10]：

(1)學生的成績表往往包含多門課程，因此學生成績發(fā)布實際上是多維敏感屬性的數(shù)據(jù)發(fā)布；

(2)敏感度與成績的高低成反比。

針對學生成績的這些特點，先前的工作提出了(L，HSC)-多樣化模型[10]。然而該模型仍然存在著一些實際的安全問題，因此本文在對先前工作分析的基礎上，提出了一種改進的學生成績發(fā)布方法，在力求簡單實用的同時，能夠保證基本的用戶隱私安全。

本文的剩余部分分為幾個內(nèi)容：第二節(jié)是對基礎知識的介紹；在第三節(jié)對(L，HSC)-多樣性進行研究和分析，指出其存在的安全漏洞；第四節(jié)在(L，HSC)-多樣性的模型的基礎上提出了一個改進的成績發(fā)布模型，并對其安全性進行了驗證；第五節(jié)是對全文的總結(jié)。

2 基礎知識

這一小節(jié)主要對相關的基礎知識進行介紹。數(shù)據(jù)表中往往包含了3類屬性。標識符是可以識別個體身份的屬性，如身份證號等，發(fā)布前經(jīng)常會進行刪除；準標識符指的是包含了個體身份信息的屬性，通過這些屬性攻擊者可以鏈接外部數(shù)據(jù)源來識別個體身份，如性別、國籍、郵編等；敏感屬性指的是包含個體隱私信息的屬性，如疾病、收入等[11]。因為本文是關于成績發(fā)布隱私保護的研究，因此敏感屬性僅指課程成績。設數(shù)據(jù)表T 包含n條記錄{t1，t2，…，tn}，每條記錄t滿足t={QI1，QI2，…，QIx，C1，C2，…，Cy}，QIi(1≤i≤x)是準標識符，Ci(1≤i≤y)為課程，也就是數(shù)據(jù)表中的敏感屬性。

定義1：L-多樣化[11]。對于數(shù)據(jù)表T及其任意一個分組G，每個敏感屬性值v(v∈Ci，1≤i≤y)在G中出現(xiàn)的頻率都不超過1/L，則數(shù)據(jù)表T在Ci上滿足L-多樣化。若T在每一個敏感屬性C 上都滿足L-多樣化，則T滿足L-多樣化。

定義2：高敏感值[10]。對于課程Ci(1≤i≤y)，假設它有|Ci|個成績(包括相同的)，Ci最低的|Ci|*HSCi個成績是Ci的高敏感值(包含第|Ci|*HSCi個低的成績)。HSCi是用戶設定的高敏感參數(shù)，根據(jù)課程的重要性，可以設定不同的高敏感參數(shù)。例如對于課程集合CourseSet={ C1，C2，…，Cy}，可以分別設置參數(shù)HSCSet={HSC1，HSC2，…，HSCy}。

定義3：(L，HSC)-多樣化[10]。如果數(shù)據(jù)表T滿足以下兩個條件，則我們認為T滿足(L，HSC)-多樣化：(1)T滿足L-多樣化；(2)對于任意課程Ci(1≤i≤y)，在任一個組G中，Ci的高敏感值的出現(xiàn)頻率都不超過1/L。

從定義3可知，(L，HSC)-多樣化能夠限制高敏感值在分組中出現(xiàn)的頻率，防止攻擊者進行敏感度上的同質(zhì)攻擊。但是在實際的應用中，(L，HSC)-多樣化模型仍然會面臨一些安全問題，下面將會進行具體的分析。

3 (L，HSC)-多樣化的回顧和分析

假設表1是原始數(shù)據(jù)表，HSC1=HSC2=HSC3=1/3，L=1/3，各個課程的高敏感值已用黑色加粗字體表示，為了簡化說明，生源地信息均用字母代替。 經(jīng)過(L，HSC)-多樣化處理后，得到表2，每個分組內(nèi)的成績被隨機打亂，同時保持各門課程成績C1，C2，C3之間的關系。(L，HSC)-多樣化限制了高敏感值在每個分組中出現(xiàn)的頻率，攻擊者最多能以1/3的概率推斷出某個學生在某門課程上取得了一個很差的成績。但是(L，HSC)-多樣化沒有考慮到一個實際可能發(fā)生的情況：課程C3的老師或課代表有在群里共享該門課程成績的習慣或C3可能通過某種方式外泄，C3的考試成績信息已經(jīng)在班級這個小范圍內(nèi)泄露，對于班級外部的攻擊者也很容易通過各種渠道獲得C3這門課程成績的信息。假設學生甲18歲，籍貫為s，攻擊者根據(jù)甲的準標識符能夠把甲定位到記錄t1，雖然在分組中的成績已經(jīng)被隨機打亂了，但是攻擊者根據(jù)泄露的C3成績知道甲的C3成績?yōu)?8分，并且各門成績之間的關系是沒有被切斷的，所以攻擊者可以很容易地推斷出甲的另外兩門課程的成績分別是56和55分。于是學生甲的隱私也就泄露了。 這就是攻擊者根據(jù)已經(jīng)泄露的部分隱私來獲取相應用戶剩余隱私信息的例子，這種情況在實際應用中也時有發(fā)生。因此針對有些課程已經(jīng)小范圍泄露或是很有可能泄露的情況，需要對學生的隱私進行進一步的保護，本文也提出了一種更加安全的改進模型。

表1 原始數(shù)據(jù)表

表2 發(fā)布后的數(shù)據(jù)表，滿足(3，1/3)-多樣化

4 (L，HSC)-多樣化+

為了解決(L，HSC)-多樣化所面臨的安全性問題，本文提出了一個改進的模型(L，HSC)-多樣化+。

4.1 基本定義

定義4 特殊課程。由于種種原因已經(jīng)發(fā)生小范圍泄漏或很可能發(fā)生泄漏的課程我們稱為特殊課程。相對于特殊課程，其他沒有發(fā)生小范圍泄漏或基本不可能發(fā)生泄漏的課程稱為普通課程。若攻擊者已經(jīng)獲取特殊課程的信息，他能根據(jù)特殊課程與普通課程之間的關系進一步地獲取學生普通課程的信息。因此在數(shù)據(jù)發(fā)布模型中需要防止這種情況的發(fā)生。

假設在數(shù)據(jù)表T中，存在課程集合CourseSet={ C1，C2，…，Ce，SC1，SC2，…，SCf}，其中Ci(1≤i≤e)為普通課程，SCi(1≤i≤f)為特殊課程，t.Ci(t.SCi)代表記錄t在課程Ci(SCi)上的分數(shù)。

(L，HSC)-多樣化+一方面要滿足(L，HSC)-多樣化的要求，還要對同組內(nèi)的特殊課程進行泛化，以防止攻擊者利用特殊課程與普通課程之間的關系來獲取學生普通課程的成績。為了使得泛化的信息損失盡可能的小，需要把在特殊課程上相似度高的記錄分在同一個組中，這里使用文獻[12]中的方法來定義距離。

因為課程成績都是數(shù)值型屬性，假設小組G={to，tp，tq}，to，tp，tq在課程SCi(1≤i≤f)上的分數(shù)分別為{a，b，c}，則泛化后這3條元組在SCi上的分數(shù)均為[min{a，b，c}～max{a，b，c}][12]。 可以看到泛化就是用抽象值代替具體值，經(jīng)過泛化后to，tp，tq有著相同的特殊課程成績，攻擊者即使獲取了某個個體的特殊課程成績也無法推斷出其的普通課程成績。

定義 5 信息損失[12]。假設泛化前t在課程SCi(1≤i≤f)上的值為[a～b]，泛化后t變?yōu)閠*，t*.SCi=[a*～b*]，則記錄t在SCi上的信息損失為：

L(t.SCi，t*.SCi)=(b*-a*+1)/(b-a+1)，t.SCi≠t*.SCi；

0，t.SCi=t*.SCi。

定義 6 元組的泛化信息損失[12]。 假設記錄t在泛化后變?yōu)閠*，則t的信息損失為：

定義了元組的信息損失，下面就可以得出元組間距離的定義：

定義 7 記錄間的距離[12]。設有記錄to，tp，tg為由它們所構成的分組的代表元組。代表元組tg的形式為{[min{to.SC1，tp.SC1} ～max{to.SC1，tp.SC1}]，[min{to.SC2，tp.SC2} ～max{to.SC2，tp.SC2}]，...，[min{to.SCf，tp.SCf} ～max{to.SCf，tp.SCf}]}。則to，tp之間的距離為：

DS(to，tp)=L(to，tg)+L(tp，tg)。

定義 8 記錄到分組的距離[12]。假設小組G={to，tp，tq}，G的代表元組tg={[min{to.SC1，tp.SC1，tq.SC1} ～max{to.SC1，tp.SC1，tq.SC1}]，

[min{to.SC2，tp.SC2，tq.SC2} ～max{to.SC2，tp.SC2，tq.SC2}]，...，[min{to.SCf，tp.SCf，tq.SCf}

～max{to.SCf，tp.SCf，tq.SCf}]}。則記錄t到G的距離為：

DS(t，G)=L(t，t*)+L(tg，t*)*|G|，

這里t*代表tg和t所構成的分組的代表元組，|G|代表分組G中記錄的數(shù)目。

定義了記錄之間、記錄和分組之間的距離，下面將給出(L，HSC)-多樣化+的實現(xiàn)算法。

4.2 算法

因為(L，HSC)-多樣化+需要滿足(L，HSC)-多樣化的要求，所以分組時在所有符合分組條件的記錄中挑選距離最近的加入當前分組。(L，HSC)-多樣化+算法結(jié)合了(L，HSC)-多樣化[10]和L-clustering[12]的特點，但是(L，HSC)-多樣化+算法事實上屬于一種局部聚類的思想，因為聚類時只需考慮記錄在部分屬性(特殊課程)上的相似性。

算法1是實現(xiàn)(L，HSC)-多樣化+的算法，在分組階段(3-10)一方面需要限制高敏感值在每個分組中出現(xiàn)的頻率，另一方面把在特殊課程上相似的記錄盡可能地聚集到同一個組中，以減少泛化帶來的信息損失。

下面以表1為例介紹(L，HSC)-多樣化+的實例。設C3為特殊課程，表1中的記錄就是按記錄包含的高敏感值數(shù)目降序排列的，所以無需重新排列。生成分組G1，順序加入第一條元組t1，因為G1現(xiàn)在并沒有在特殊課程上包含高敏感值，所以順序選擇一條能滿足算法1第7行那兩個性質(zhì)的記錄-t3加入G1?，F(xiàn)在G1已經(jīng)在特殊課程C3上包含了高敏感值68，構造集合Q={t5，t6}.G1當前的代表元組為tg=[68～78]，t5與tg形成的分組的代表元組為t*=[68～80]，t5到G1的距離DS(t5，G1)=DS(t5，t*)+|G1|*DS(tg，t*)=13+2*13/11=13+2.36=15.36。同樣的計算t6到G1的距離DS(t6，G1)=DS(t6，t*)+|G1|*DS(tg，t*)=12+2*12/11=14.18，這里的t*是t6和tg形成分組后的代表元組，t*=[68～79]。因為DS(t6，G1)

為了方便分析特殊課程的抽象值和普通課程之間的關系，也可以把特殊課程的泛化值轉(zhuǎn)換成區(qū)間的形式(即用數(shù)值型屬性的泛化方法[12]來泛化)，得表4。例如，通過對表4的分析可以知道，C3分數(shù)在(68-79)之間的學生，C2的分數(shù)往往不如C3分數(shù)在(73-80)之間的學生理想。

4.3 算法分析

正確性分析。算法的分組階段(3-10)要求每個分組在每門課程上最多只能包含一個高敏感值，且至少有L個不同的分數(shù)，這也就確保了高敏感值在分組中出現(xiàn)的頻率不會超過1/L，且發(fā)布的數(shù)據(jù)表能滿足L-多樣化的要求。當分組在特殊課程上不包含高敏感值時，不會進行局部聚類，是為了避免給后面生成的分組留下過多特殊課程上的高敏感值。

時間復雜度分析。設數(shù)據(jù)表中有n條記錄，CourseSet={C1，C2，…，Ce，SC1，SC2，…，SCf}，最后分成了m個組。

第1行：計算每門課程的高敏感值最多需要O(n2)，有e+f門課程，所以最多需要O(n2*(e+f))。

分組階段：對于每個分組G，在最壞的情況下，每次都要進行局部聚類。對數(shù)據(jù)表T排序最多需要O(n2)(第3行)，G每次加入一條記錄，最多需要O(n(e+f))來建立Q(第7行)，從Q中挑選一條離G最近的記錄最多需要O(nf)，當|G|≥L時G生成完畢，故生成一個分組G最多需要O(n2)+O(L(e+2f)n)，生成m個分組需要O(mn2)+O(L(e+2f)nm)。

處理剩余記錄階段：對于每一條剩余記錄t，構建P最多需要O(m(e+f))，尋找一個離t最近的分組最多需要O(mf)，因此處理一條剩余記錄需要O((e+2f)m)。共有n-mL條剩余記錄，所以這個階段最多花費O((n-mL)(e+2f)m)。

發(fā)布階段：每個組G中，隨機打亂成績順序需要O(2|G|)，泛化特殊課程成績需要O(|G|*f)。所以這個階段需要O((2+f)n)。

綜上所述，算法1最多需要時間O(n2*(e+f))+O(mn2)+O(L(e+2f)nm)+O((n-mL)(e+2f)m)+O((2+f)n)。

4.4 安全性分析

因為特殊課程成績已經(jīng)泛化，分組中每個記錄都有著一個相同的抽象特殊課程成績，即使攻擊者獲得了某個學生的特殊課程的成績，也無法根據(jù)已知的隱私信息去推斷出該學生的普通課程成績。即特殊課程的泄露無法給攻擊者獲取相應個體的普通課程成績帶來任何幫助。由此可見，(L，HSC)-多樣化+適用于在某些課程成績已經(jīng)小范圍泄露或可能發(fā)生泄漏的情況，能夠給學生帶來更好的隱私保障。

此外，雖然特殊課程與普通課程之間的直接關系被切斷，但是部分的聯(lián)系仍然得以保存。也就是說，(L，HSC)-多樣化+并沒有完全切斷特殊課程和普通課程之間的聯(lián)系，仍然保存著特殊課程上的抽象值與普通課程之間的關系，就如4.2中所列舉的例子。

表3 發(fā)布的數(shù)據(jù)表滿足(HSC，L)-多樣化+，HSC1=HSC2=SCHSC=1/3，L=3

表4 發(fā)布的數(shù)據(jù)表滿足(HSC，L)-多樣化+，HSC1=HSC2=SCHSC=1/3，L=3

算法1:(L,HSC)-多樣化+輸入?yún)?shù):L,普通課程的高敏感參數(shù){HSC1,HSC2,…,HSCe},特殊課程的高敏感參數(shù){SCHSC1,SCHSC2,…,SCHSCf},原始數(shù)據(jù)表T輸出:發(fā)布的數(shù)據(jù)表T*1.根據(jù)高敏感參數(shù)計算每門課程的高敏感值;//分組階段2.當T中的記錄還能構成分組,重復3-10:3.按記錄包含高敏感值的數(shù)目對T做降序排列;4.建立一個新的分組G,加入T中的第一條記錄t,T-t;5.若G在某一個SC上存在高敏感值,執(zhí)行6,否則直接執(zhí)行10;6.當G中的記錄數(shù)小于L,重復7-8:7.建立集合Q,Q中的記錄t～(t～∈T)均滿足以下性質(zhì):(1)對于任一條記錄t∈G,在任一個課程Ci(SCi)上,都不存在t～.Ci(SCi)=t.Ci(SCi);(2)若G在Ci(SCi)上已經(jīng)存在了高敏感值,則t～.Ci(SCi)不是高敏感值。8.在Q中尋找一條離G最近的記錄tmin,G∪tmin,T-tmin;9.T*∪G,返回2;

10.順序挑選一條元組t～,t～滿足7中的兩個性質(zhì),G∪t～,T-t～,若|G|≥L,返回9,否則,返回5;//處理剩余記錄階段11.對于T中的每一條記錄t,執(zhí)行12-13:12.P為分組的集合,每個P中的分組G均滿足:t加入G后,G在每個課程Ci(SCi)上仍然最多只有一個高敏感值;13.從P中尋找一個離t最近的G,G∪t,T-t;//發(fā)布階段14.對于T*的每個分組G,隨機打亂G中成績的順序,同時保持各門成績之間的關系,泛化特殊課程的成績,最后發(fā)布T*。

5 總結(jié)

學生成績發(fā)布對學生學習情況的分析、教學決策等方面都有著重要的意義，但是現(xiàn)存的學生成績發(fā)布模型都沒有考慮到一些現(xiàn)實中的安全問題。結(jié)合實際情況，本文在先前工作的基礎上提出了一個改進的學生成績發(fā)布模型。該模型考慮了某些課程已經(jīng)小范圍泄漏或可能發(fā)生泄漏的情況，采取了相應的保護措施，在保持模型簡單實用的前提下，進一步地保證了學生的隱私安全。

[1]L Sweeney.k-anonymity：a model for protecting privacy[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，10(5)：557-570，2002.

[2]L Sweeney.Achieving K-anonymity privacy protection using generalization and suppression[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，10(5)：571-588，2002.

[3]A Machanavajjhala，J Gehrke，D Kifer，M Venkitasubramaniam.L-diversity：privacy beyond k-anonymity[J].Proceedings of the 22nd International Conference on Data Engineering(ICDE ’06)，24-26，April，2006.

[4]X Xiao，Y Tao.Anatomy：simple and effective privacy preservation[J].Proceedings of the 32nd International Conference on Very Large Data Bases(VLDB ’06)，139-150，Seoul，Republic of Korea，September 2006.

[5]童云海，陶有東，唐世渭.隱私保護數(shù)據(jù)發(fā)布中身份保持的匿名方法[J].軟件學報，2010，21(4)：771-781.

[6]Ahmed Abdalaal，Mehmet Ercan Nergiz，Yucel Saygin.Privacy-preserving publishing of opinion polls [J].Computers & Security，2013(37)：143-154.

[7]Yang Ye，Yu Liu，Dapeng Lv，Jianhua Feng.Decomposition：Privacy Preservation for Multiple Sensitive Attributes[J].Database Systems for Advanced Applications，2009.

[8]張冰，楊靜，張健沛，謝靜.面向敏感性攻擊的多敏感屬性數(shù)據(jù)逆聚類隱私保護方法[J].電子學報，2014，42(5)：896-903.

[9]龍琦.基于k - 匿名技術的學生成績數(shù)據(jù)發(fā)布研究[J].云南民族大學學報(自然科學版)，2011，20(3)：144-148.

[10]Yi T，Shi M，Hong Z.Privacy Protection Method for Test Score Publishing[C].International Conference on Information Technology in Medicine and Education，IEEE Computer Society，2015，516-520.

[11]楊曉春，王雅哲，王斌，于戈.數(shù)據(jù)發(fā)布中面向多敏感屬性的隱私保護方法[J].計算機學報，2008，31(4)：574-587.

[12]王智慧，許儉，汪衛(wèi).一種基于聚類的數(shù)據(jù)匿名方法[J].軟件學報，2010，21(4)：680-693.

(責任編輯：宋金寶)

A Simple Data Publication Method for Student Achievement

YI Tong，SHI Min-yong

(School of Computer Science，Communication University of China，Beijing 100024，China)

The analysis of student achievement can provide valuable information for teaching model reform.When analyzing the academic achievement，the private of students should be protected.So a safe and effective data publication method for student achievement is needed.This paper provides a simple practical student achievement publication method based on previous work and verifies its security.

student achievement；privacy；security；data publication

2016-06-27

易通(1987-)，男(漢族)，廣西玉林人，中國傳媒大學博士生.E-mail：549679609@qq.com

TP309.2

A

1673-4793(2017)03-0019-06