Finding Exact-Match Answers
There are two types of plagiarism that can be found on Stack Overflow: exact-match instances, and non-exact-match instances. Of the two types, exact-match plagiarism is relatively trivial to detect: it merely requires a simple equality comparison between two "strings" (or whatever text-field datatype is being used to store answers in a particular database).
When detecting exact-match instances of plagiarism on Stack Overflow, the "hard part" comes in efficiently surfacing these cases from the database, i.e. the Stack Exchange Data Explorer (SEDE).
A Naive Approach
Here is a naive query that can be run against SEDE to find exact-match answers,
SELECT u.Id AS [User Link],
p1.Score,
FORMAT(p1.CreationDate, 'yyyy-MM-dd') AS [Date],
p1.Id AS [Post Link],
p2.Id AS [Post Link]
FROM Posts p1 INNER JOIN Posts p2 ON p1.Body = p2.Body -- SUBSTRING(p1.Body, 0, 100) = SUBSTRING(p2.Body, 0, 100)
INNER JOIN Users u ON p1.OwnerUserId = u.Id
WHERE p1.PostTypeId = 2 AND p2.PostTypeId = 2 -- 2 is the post type for answers
AND DATEDIFF(month, u.CreationDate, GETDATE()) <= ##MaxMonthAge:int?12##
AND p1.Id <> p2.Id
AND p1.OwnerUserId <> p2.OwnerUserId
AND p1.CreationDate BETWEEN ##StartDate:string?2013-01-01## AND ##EndDate:string?2015-12-31##
AND p2.CreationDate < p1.CreationDate
AND p2.CreationDate <= ##EndDate:string?2015-12-31##
AND ##MinLength:int?100## <= LEN(p1.Body)
ORDER BY u.Id,
p1.Score DESC,
[Date]
The key part of this query is the self-join of the Posts table on itself, using the equality of two post bodies as the condition for the join,
FROM Posts p1 INNER JOIN Posts p2 ON p1.Body = p2.Body
Note that in this query, user u represents a potential plagiariser, p1 represents a potentially plagiarised answer, and p2 represents the (possible) original source. Thus, the following conditionals filter the set of self-joined post bodies down to those where
- The post bodies are an exact match.
- The posts are answers.
- The answer IDs aren't the same (don't include the join of an answer with itself).
- The answer owners are different.
p1 was created after p2, i.e. p2.CreationDate < p1.CreationDate.
Expressed in SQL, these are
WHERE p1.PostTypeId = 2 AND p2.PostTypeId = 2 -- 2 is the post type for answers
-- ...
AND p1.Id <> p2.Id
AND p1.OwnerUserId <> p2.OwnerUserId
-- ...
AND p2.CreationDate < p1.CreationDate
When running such a query against a data set as large as SEDE, I found it helpful to also add the following conditionals to limit the result set, making the query run faster, but at the cost of potentially missing some instances of plagiarism,
- For a user
u, only return results if that user's account is less than X months old. The idea behind this is that "new" user accounts are more likely to engage in plagiarism than accounts belonging to more established users...though in some cases, I have found high-rep users with accounts that are years old, who have engaged in a disappointingly large number of instances of plagiarism.
- Limit potential positive
p1 to answers made within a certain time frame.
- Limit potential source
p2 to answers created before a certain date.
- Limit potential matches to the ones where the post bodies are at least
X characters long, with the idea being that short answers are more likely to be false positives.
Expressed in SQL, these conditionals are
AND DATEDIFF(month, u.CreationDate, GETDATE()) <= ##MaxMonthAge:int?12##
-- ...
AND p1.CreationDate BETWEEN ##StartDate:string?2013-01-01## AND ##EndDate:string?2015-12-31##
-- ...
AND p2.CreationDate <= ##EndDate:string?2015-12-31##
AND ##MinLength:int?100## <= LEN(p1.Body)
Try It Out
You can test out the above query on SEDE. I have given the query some default parameters that will currently return results (about 140 of them, to be exact), though if moderators start removing true positives, then the result set may eventually be reduced to zero.
Feel free to play around with the parameters, or even make modifications to the query itself.
Finding Exact-Match Answers by Location
As another technique to make querying a large data set such as SEDE more practical, it can be helpful to limit the number of answers that are compared by narrowing them down to users who are more likely to plagiarise than your average Stack Overflow user. One such criteria that can be effectively employed is a user's location:
SELECT p.Id, p.OwnerUserId, p.Body, p.CreationDate, p.Score
INTO #Answers
FROM Users u INNER JOIN Posts p ON u.Id = p.OwnerUserId
WHERE p.PostTypeId = 2 -- answers
AND u.Location LIKE '%FILL IN LOCATION HERE%'
SELECT -- TOP ##Limit:int?100##
ROW_NUMBER() OVER (ORDER BY a.OwnerUserId, a.Score DESC, a.CreationDate) AS Rank,
a.OwnerUserId AS [User Link],
FORMAT(u.Reputation, '#,###') AS Reputation,
a.Id AS [Post Link],
p.Id AS [Post Link],
a.Score,
DATEDIFF(day, a.CreationDate, GETDATE()) AS [Days]
FROM Posts p INNER JOIN #Answers a ON p.Body = a.Body
INNER JOIN Users u ON a.OwnerUserId = u.Id
WHERE p.PostTypeId = 2 -- answers
AND p.Id <> a.Id
AND p.OwnerUserId <> a. OwnerUserId
AND p.CreationDate < a.CreationDate
ORDER BY a.OwnerUserId, a.Score DESC, a.CreationDate
This query first creates a temporary table #Answers, populating it with answers (and meta-data) for users from a certain location (forgive me if "temporary table" is not the right term, my Transact-SQL is a little rusty). After creating the #Answers table, a second query (similar to the one presented in the previous section above) is used to find exact-match answers that are potentially an original source.
Note that the Location being used in this query is what users choose to make public in their profiles. If a user does not populate this field in their profile, then they will never be included in the query results.
Finding Serial Plagiarisers
Using the tools and techniques that I have presented above (or using your own methods), you may come across a legitimate instance of plagiarism. I have often found it to be the case that when a user plagiarises once, they are likely to plagiarise many times. It can be an extremely time consuming process, but if you are feeling so inclined, you might decide to check a known plagiariser's other answers to see if they too are additional cases of plagiarism.
In the case of exact-match answers, this process can be automated somewhat by using a query such as the following,
DECLARE @lastEditDate datetime2 = (
SELECT MAX(LastEditDate)
FROM Posts
WHERE OwnerUserId = ##UserId:int## AND PostTypeId = 2 -- answers
)
SELECT ROW_NUMBER() OVER (ORDER BY p1.Score DESC, p1.CreationDate) AS Rank,
p1.Id AS [Post Link], p1.Score, DATEDIFF(day, p1.CreationDate, GETDATE()) AS [Days], p2.Id AS [Post Link]
FROM Posts p1 INNER JOIN Posts p2 ON p1.Body = p2.Body
WHERE p1.PostTypeId = 2 AND p2.PostTypeId = 2 -- answers
AND p1.Id <> p2.Id
AND p1.OwnerUserId <> p2.OwnerUserId
AND p1.OwnerUserId = ##UserId:int##
AND p2.CreationDate < @lastEditDate -- don't check answers that are newer than the user's last edit date
ORDER BY p1.Score DESC, p1.CreationDate
This query returns the entire set of potentially plagiarised exact-match answers for a given user. Much like the very first query I presented, it does a self-join of the Posts table, using equal text-bodies as the join-condition. A key addition, however, is the condition that narrows the search results down to answers belonging to a specific user (the known plagiariser),
AND p1.OwnerUserId = ##UserId:int##
As I mentioned, this query only returns exact-match cases of plagiarism. If a known plagiariser (also) uses non-exact-match answers, then you might just have to find original sources manually by using Google and SO's search engine, as I have mentioned.
Can You Improve These Queries (or Make Better Ones)?
There are many areas of improvement to the SQL queries that I have presented, such as making them run more efficiently, or returning a more complete and exhaustive set of results. One interesting enhancement might be to modify the queries to search the revision history for answers, in case an original source and a copy "drift" away in similarity as a plagiariser (or well meaning SO users) edit them over time.
Another simple enhancement would be to strip HTML and Markdown formatting from the post bodies before comparing them. Someone also once suggested using the Levenshtein distance between posts for comparison.
Also, I am not a source control expert, and I would be interested to know if any text comparison techniques used in version control can be applied to this problem. I've also heard about tools that people working in academia use to determine whether a student's paper has been plagiarised from some other source, and I would be interested in hearing about whether these tools can detect non-exact-matches, and about whether their algorithms can be applied to this problem.
Update: Calculating Levenshtein Distance and SEDE
I read up on how Levenshtein Distance is calculated, and it seems too computationally expensive to implement in a SEDE query. I might just make a GitHub project in .NET or Ruby someday that implements this instead (perhaps with an additional public-facing web interface that people can use).
In the meantime, here's a pseudo-code description of the algorithm, along with my notes, derived from the English description in Levenshtein Distance, in Three Flavors. Note that my pseudo-code style is a mish-mash of mathematical notations and syntaxes borrowed from a variety of languages, e.g. Haskell, Ruby, Java/C# etc.
/*
* - Each iteration of the `for` loops computes the Levenshtein Distance for
* the sub-matrix that begins at cell M(1,1) and terminates at cell M(i,j).
* - Addition and deletion are inverses of each other, and modify string length.
* - Substitution can only occur along diagonals, i.e. iff index i == j, and
* does *not* modify string length.
* - Algorithm uses 1-based matrix/array indexing, not 0-based.
*/
EditDistance(string a, string b) -> int
{
int n = a.length
int m = b.length
return m if n == 0 // `a` is empty string
return n if m == 0 // `b` is empty string
M = new Matrix(n,m)
int cost = 0
for int i from 1 to n {
for int j from 1 to m {
cost = (0 if a(i) == b(j)) else 1
M(i,j) = min(M(i - 1, j) + 1, M(i, j - 1) + 1, M(i - 1, j - 1) + cost)
}
}
return M(n,m)
}
Update: Have My Edits Been Rolled-Back?
Occasionally, when you're searching for plagiarism, you'll come across answers that technically cite the source(s) that they're copied from, but do so poorly. For example, by not using quote-formatting, and "hiding" the source link at the very bottom of the answer, in non-descriptive anchor text like "SEE THIS" or "LINK".
Such answers come across as a little dishonest because they're not very forthright about the fact that they're copied from another source. Indeed, I have actually mistaken such answers for plagiarism at first glance.
In such cases, you may want to help the answer author improve his/her citation of the copied source through editing. Even in the case of actual plagiarism, you may want simply cite the source for the author, rather than flag him/her for plagiarism.
It has been my experience, however, that sometimes the owners of these plagiarised and almost-plagiarised answers will later undo such edits. In order to make it easier to determine if such a rollback has occurred, I have written another SEDE query that takes your Stack Overflow user-id, and returns all of your edits (made in the last X days) that have been replaced by subsequent edits. Enjoy!
SELECT ph.Id, ph.PostId, ph.CreationDate, ph.Comment
INTO #Edits
FROM PostHistory ph
WHERE UserId = ##UserId:int##
AND ph.PostHistoryTypeId IN (5,8) -- Edit, or Rollback
AND DATEDIFF(day, ph.CreationDate, GETDATE()) <= ##MaxDayAge:int?14##
SELECT ph.PostId AS [Post Link], ph.CreationDate
FROM PostHistory ph INNER JOIN #Edits e ON e.PostId = ph.PostId
WHERE ph.PostHistoryTypeId IN (5,8) -- Edit, or Rollback
AND e.CreationDate < ph.CreationDate -- new revision
ORDER BY ph.CreationDate DESC
A note on answers with poor citation
When you see an answer that poorly cites a copied source, you may in fact want to check the revision history to see if in fact it was originally plagiarised. It has also been my experience that sometimes someone other than the answer poster will come along and cite the plagiarised source for the plagiariser. If you find an answer like that, you may want to investigate the author's other answers for signs of more plagiarism.
