Re: [問卦] 有沒有程式設計課抓作業抄襲的八卦？消失
※ 引述《snaketsai (さいでんし)》之銘言：
: 先說，小弟不是這塊專門，
: 純粹今天參加研討會回到旅館、腦袋很累但又睡不著
: 湊巧看到這篇文章
: 隨便看看文件（只快速看了15 min）隨便講而已
: 所以一定有講錯，但也還請板上神人能夠幫忙簡介XD
: (表示想聽別人消化完的版本QQ)
: 某些大學的數位教學平台(e.g. Moodle)
: 助教的系統那邊可能會串一些抄襲偵測的服務
: 直接 n取2 抓起來比對
: 其中學術用免錢的後端，以Stanford的MOSS(Measure Of Software Similarity)
: 系統最為常見
: 而它背後理論基礎的論文是這篇：
: 《Winnowing: Local Algorithms for Document Fingerprinting》
: 從標題便可發現其實它的本質應該還是文本分析，而非真正去理解程式結構
: 那篇論文的重點就在針對局部文本比對加上winnowing
: 首先是一般的Karp-Rabin字串比對，
: 這演算法提出兩個常數來規範它的偵測敏感度：
: (1)小於K長度字串的重複不計。
: 白話文來說就是：
: 假如一直抓「的」這個字，是沒有意義的，因為文章中這字出現頻率超高
: (2)長度大於T的字串重複視為抄襲的保證下限。
: 白話文就是：
: 一大段字完全一模一樣，你說這不是抄襲騙誰啊？
: 很直觀地，T一定要大於或等於K
: 現在假定一個抄超長句子，以K為單位做K-gram後、取雜湊的雜湊值的序列為：
: h1 h2 h3 h4 ... hn
: 且n比(t-k)大
: 這篇論文的作者覺得必定存在一段子句(先稱作hi)是足夠代表整個句子
: 亦即不論你從h1~hn中怎麼圈選子句子來聲稱：
: 「因為A文件中的一個句子S1的子句S1'
: 符合B文件中的另一個句子S2的子句S2'
: 所以我們認為S1跟S2是同一句話」
: 那S1'跟S2'一定包含hi這段指紋子句
: 現在再提出一個常數W為T-K+1，代表雜湊值的比對窗口大小
: 以W為窗口，每次位移一格取出雜湊值k-gram
: 接下來就是它的重點Winnowing了：
: 第一次取第一個窗口中最小的雜湊值，放進指紋名單、並且當作 目前指紋。
: 接下來第二個窗口中一樣取最小，跟上一次的 目前指紋 比較；
: 一樣的話：若在該窗口最右邊還是取，若不是在最右邊則拋棄，
: 不一樣的直接放進指紋名單、變成新的目前指紋。
: （原文看沒有很懂，我是看別人的實做跟論文例子推想）
: 有了指紋名單，接下來就是從另外一個文件中取出指紋子句了
: 如果兩邊重複越多，那自然合理判斷為越像
: 至於怎麼斷句，切成不同的部份，在這篇論文又是另外一個主題
: = = = =
: 以論文中的舉例來跑一次，今天有一個句子被餵進演算法裡面——
: A do run run, a do run run.
: 會先被去掉不影響分析的不相關特徵，e.g. 標點符號、大小寫差異— —
: adorunrunadorunrun
: 接下來設K為5，做出5-gram (亦即5個為一單位，每次往後一格取完所有子字串)
: adoru dorun orunr runru unrun nrunr runru
: unrun nruna runad unado nador adoru dorun
: orunr runru unrun
: 假定對每單位取完雜湊長這樣：
: 77 74 42 17 98 50 17 98 8 88 67 39 77 74 42
: 17 98
: 設T為8，那窗口W按上述說明為4，將雜湊取4-gram
: 並且做Winnowing，被選出來的我用紅色標注
: (77, 74, 42, 17) (74, 42, 17, 98)
: (42, 17, 98, 50) (17, 98, 50, 17)
: (98, 50, 17, 98) (50, 17, 98, 8)
: (17, 98, 8, 88) (98, 8, 88, 67)
: ( 8, 88, 67, 39) (88, 67, 39, 77)
: (67, 39, 77, 74) (39, 77, 74, 42)
: (77, 74, 42, 17) (74, 42, 17, 98)
: 所以我們得到了特徵值名單：
: 17, 17, 8, 39, 17
: 接下來......接下來就是怎麼從另一份文件選出子句來；
: 跑同樣流程然後比對有沒有相同指紋的事情了(逃)
: 坦白說我是覺得還滿意外MOSS的基礎是這樣有點純文本分析味道的產物
: 一直以來我都以為他可能會把兩份程式各長出一顆AST、然後比樹的相似度之類的
: 這種作法在資料流分析也不算少見、對程式碼混淆的抵抗力也很高
: 不過缺點就是出題太簡單的話，不是抄襲也會長太像被誤判
: 當然，就如我文章開頭所述，我是在腦袋很亂睡不著時亂看的
: 很可能一覺醒來發現我根本搞錯這篇paper想幹麻
: 而我也相信板上神人這麼多，一定有人看過MOSS的原理
: 還請看到的您不吝分享 <(_ _)>
: 真的該洗洗睡了Orz
不太清楚 MOSS 的原理
這樣還是文字比對吧 ?
一般人抄作業 不都是變數名稱改一下
用 search and replace all 來替換嗎?
這樣還抓得到嗎?
要抓程式抄襲 應該是要寫 front end parser 吧?
先把程式轉成 CFG (context free grammar)
再轉成語法樹 syntax tree
用樹狀比對 抓相似的節點吧?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.54.156
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1476232423.A.D9F.html
推
10/12 08:47, , 1F
10/12 08:47, 1F
→
10/12 09:15, , 2F
10/12 09:15, 2F
推
10/12 09:18, , 3F
10/12 09:18, 3F
推
10/12 09:30, , 4F
10/12 09:30, 4F
推
10/12 10:14, , 5F
10/12 10:14, 5F
推
10/14 18:43, , 6F
10/14 18:43, 6F
推
10/22 05:36, , 7F
10/22 05:36, 7F
→
10/22 05:37, , 8F
10/22 05:37, 8F
→
10/22 05:37, , 9F
10/22 05:37, 9F
→
10/22 05:38, , 10F
10/22 05:38, 10F
→
10/22 05:38, , 11F
10/22 05:38, 11F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：