Git Blame Who?: Stylistic Authorship Attribution of Small, Incomplete Source Code Fragments Edwin Dauber Aylin Caliskan Richard Harang Rachel Greenstadt Drexel University Princeton University Invincea Drexel University 7 1 Abstract—Programauthorshipattributionhasimplicationsfor made by one of their employees? Past work has shown that 0 the privacy of programmers who wish to contribute code files written by a single individual are attributable, but most 2 anonymously. While previous work has shown that complete opensourceprojects,likemostprofessionalcode,iswritten r files that are individually authored can be attributed, we and revised collaboratively. a show here for the first time that accounts belonging to open Assuming a known set of suspect programmers, such M sourcecontributorscontainingshort,incomplete,andtypically as the employees of a company, and some form of seg- uncompilable fragments can also be effectively attributed. mentation and grouping by authorship, such as accounts 6 We propose a technique for authorship attribution of on a version control system, we present a technique which 1 performs stylistic authorship attribution of a collection of contributor accounts containing small source code samples, partialsourcecodesampleswrittenbythesameprogrammer ] suchasthosethatcanbeobtainedfromversioncontrolsystems G with up to 99% accuracy for a set of 106 suspect program- or other direct comparison of sequential versions. We show mers. By contrast, the current state-of-the-art technique for L that while application of previous methods to individual small source code attribution achieves an individual accuracy of . source code samples yields an accuracy of about 73% for 106 s at most 73% under standard circumstances. We also present c programmers as a baseline, by ensembling and averaging the a technique using the classifier’s output probability, or con- [ classificationprobabilitiesofasufficientlylargesetofsamples fidence, to address the open world problem in which the belonging to the same author we achieve 99% accuracy for 2 true programmer could be someone outside of the suspect v assigning the set of samples to the correct author. Through set.Weconstructcalibrationcurvestoindicatetheaccuracy 1 these results, we demonstrate that attribution is an impor- forcollectionswhichwereattributedwithgivenconfidence, 8 tant threat to privacy for programmers even in real-world and analysts can use these curves to set a threshold below 6 collaborative environments such as GitHub. Additionally, we which to more carefully examine authorship due to higher 5 propose the use of calibration curves to identify samples by 0 probabilityofbeingoutsideofthesuspectset[21].Wethen unknown and previously unencountered authors in the open . proceed to show how this calibration curve can be used 1 world setting. We show that we can also use these calibration at the level of individual samples to mitigate the cost of 0 curvesinthecasethatwedonothavelinkinginformationand misattributionintheabsenseofgroupingofsamples.Inthis 7 thus are forced to classify individual samples directly. This 1 scenario, the threshold will need to be set higher to catch is because the calibration curves allow us to identify which : most misattributions, and will cause a larger percentage of v samplesaremorelikelytohavebeencorrectlyattributed.Using correctly attributed samples to require review. i X such a curve can help an analyst choose a cut-off point which This work is valuable standalone, but even more im- r will prevent most misclassifications, at the cost of causing the portant as validation that source code authorship segmenta- a rejection of some of the more dubious correct attributions. tion is possible. Segmentation naturally exists with version control on public repositories, and there are real world use 1. Introduction scenarios for performing authorship attribution on accounts onsuchrepositories.Forcollaborativelywrittencodewhich Many employees of large companies have clauses in is not managed on such repositories, we present our high their contracts which claim that all of their related work is accuracy as evidence that it is reasonable to expect that the intellectual property of the company. For programmers, segmentation at a reasonable level is possible. this means any source code produced during their employ- Previous work has attributed authorship to whole code mentcouldbeclaimedbythecompany.Theseprogrammers filescollectedeitherfromsmallsuspectsetsorfromdatasets are then contractually required to get explicit permission which are near to laboratory condition, such as single to contribute to open source projects, and failing to do so authored code submitted to the Google Code Jam [2], can result in termination. Recently, the legality and reality [6]. While there are real-world applications for this work, of this situation has been a topic of discussion and debate it ignores the difficult properties of code written “in the on Twitter [29]. But is it really possible for an employer wild”.Bycontrast,weexaminesmallsamplesofrealworld to determine if anonymous open source contributions were sourcecodecollectedfromtheonlinecollaborativeplatform GitHub and show high accuracy attributing the author from all past attempts at source code authorship attribution have a suspect set of over 100 programmers [1]. This addresses worked with complete code samples which solve some knownweaknessesinpastwork1andopensnewpossibilities problem,whileweworkwithsmallbuildingblocksofcode forfuturework.Wenotethatthesamplesweworkwithcan which are often not a complete solution to anything. beassmallasasinglelineofcode,andsocancontainvery The most critical piece of prior research related to our little information with which to determine authorship. We work is the work of Caliskan-Islam et al. using random also present a technique to handle the open world problem, forests to perform authorship attribution of Google Code which has been minimally explored in previous work. Jam submissions, with features extracted from the abstract In this paper, we demonstrate attribution under various syntax tree [9]. We use their feature set and classification scenarios.Theeasiestscenario,whichwerefertoasmultiple method as the base for our work, but rather than look at sample attribution, features the closed world assumption, complete source code files we look at small pieces of code underwhichweknowthattheauthorisamongoursuspects, that have been attributed to individual authors by use of andtheversioncontrolassumption,underwhichweassume git blame. As a result of focusing on small segments of thatthemulti-authoredcodefileissegmentedandthoseseg- code, our feature vectors are much more sparse and we are ments are grouped by (unknown) author. Then we remove unable to prune the feature set through use of information the closed world assumption and address the open world gain as they did. Their work also looks at the open world versionofmultiplesampleattribution.Wealsoshowresults problem,andusesclassificationconfidencetosetathreshold with a relaxed version of the version control assumption below which to reject classifications. Further, their work is which only assumes segmentation, and not grouping, for with data from Google Code Jam, which as a programming comparison purposes and to demonstrate the usefulness of competitioncreateslaboratoryconditionsforthedata,while thecalibrationcurve.Werefertothisversionoftheproblem our work is on data from GitHub, giving us real world as single sample attribution, and observe it both under the conditions. We demonstrate that their techniques can be closed world assumption and in the open world. adapted to handle more difficult attribution tasks which In this paper, we experiment with several subsets of are of interest in real world situations and have not been GitHub data. Our first subset contains 15 programmers, and previously examined. with this dataset we can perform single sample attribution Therearemanyotherproposedmethodsandfeaturesets withaccuracynear70%withacalibrationcurveidentifying for source code de-anonymization, but those methods had confidence levels which are highly accurate. We can also worse accuracy and smaller suspect sets. Therefore, while achieve nearly 97% accuracy with groups of 5 samples combiningthesetechniquesmayallowustoboostaccuracy, and 100% accuracy with groups of 35 or more samples for the purposes of this work we do not consider them for multiple sample attribution. Our second main subset further.Frantzeskouetal.usedbyteleveln-gramstoachieve contains 106 programmers, and with this dataset we can high accuracy with small suspect sets [13], [14], [15]. The perform single sample attribution with 70% accuracy and use of abstract syntax trees for authorship attribution was multiplesampleattributionwithaccuracyover95%foreven pioneered by Pellin and used on pairs of Java programs pairsofsamples,and99%forgroupsofatleast15samples. in order to ensure that the studied programs had the same Further, we show that even weak classifiers which achieve functionality [23]. Ding and Samadzadeh studied a set of only38%accuracyforsinglesampleattributioncanachieve 46 programmers and Java using statistical methods [10]. over 90% accuracy for multiple sample attribution with sets MacDonnel et al. analyzed C++ code from a set of 7 of at least 10 samples. professional programmers using neural networks, multiple discriminant analysis, and case-based reasoning [19]. Bur- 2. Related Work rows et al. proposed techniques that achieved high accuracy for small suspect sets, but had poor scalability [6], [7], [8] We observe two primary categories of related work. We Spafford and Weeber were among the first to suggest draw on past work in the area of source code authorship performingauthorshipattributiononsourcecode[25].How- attribution, and then we look at some critical work in the ever, while they proposed some features to do so, they area of plaintext authorship attribution. While the two do- did not propose an automated method nor a case study. mains have evolved different feature sets and classification Hayes and Offutt performed a manual statistical analysis techniques, recent work in text authorship attribution is of 5 professional programmers and 15 graduate students, closely related to our work. and found that programmers do have distinguishable styles which they use consistently [16]. For our ground truth we use git blame to assign author- 2.1. Source Code Authorship Attribution ship to individual lines of code. Git blame is a heuristic which attributes code to the last author to modify that code. An important overall note about related work is that Meng et al. proposed a tool called git-author which assigns we are the first to attempt attribution of short, incomplete, weighted values to contributions in order to better represent andtypicallyuncompilablecodesamples.Toourknowlege, the evolution of a line of code [20]. This tool creates a repository graph with commits as nodes and development 1.“I will believe that code stylometry works when it can be shown to workonbiggithubcommithistoriesinsteadofGCJdataset”[12] dependencies as edges, and then defines strucutral author- ship and weighted authorship for each line of code, where they consider is classifier confidence. We apply the same structural authorship is a subgraph of the respository graph intuition to source code to determine which classifications withrespecttothatlineofcodeandweightedauthorshipisa to trust and which to reject. vector of programmer contributions derived from structural authorship. 3. Methodology 2.2. Text Authorship Attribution Our method is summarized in Figure 1. We begin by The primary piece of related research in the domain collecting C++ repositories on GitHub, and then break- of text authorship attribution is the work by Overdorf and ing collaborative files from those repositories into smaller Greenstadtincross-domainauthorshipattribution[22].This pieces using git blame. The details of this are described in work links authorship between blogs, tweets, and reddit Section 3.2. For each individual piece of code, we extract comments. This work is related to ours in two primary the abstract syntax tree and use that to extract a feature ways. First, and most obviously, they work with short text vector, as described in Section 3.3. We then proceed to in the forms of tweets and reddit comments. For these perform attribution of each sample using a random forest domains, they use a technique of merging text before ex- as described in Section 3.4. Then we average the classifier tracting features. We propose a similar merging technique, probabilityoflinkedsamplesasdescribedinSection3.5and although we merge after extracting features rather than construct a calibration curve as described in Section 3.6. before. More significantly, they also use a method of av- eraging the probabilities for multiple samples to classify collectionsofsamples.Wedemonstratethatthistechniqueis 3.1. Problem Statement similarly applicable in the source code domain, and that we get excellent results even with averaging a small number In this paper we consider ourselves to be in the role of of samples. Additionaly, they make no effort to classify the analyst attempting to attribute source code and break individual tweets, while we successfully classify samples anonymity. We assume that the collaboratively written code of code as short as a few lines. we are examining has been pre-segmented by author. This Our work is also related to research in the area of text segmentation may be from version control commits, git segmentation. Akiva and Koppel proposed an unsupervised blame, or some other method of decompositon; we only method to identify the author of individual sentences in an assumethatwehavesmallsampleswhichcanbereasonably unsegmented multi-authored document, as a generalization attributed to a single individual. We also assume that we of previous work by Koppel et al. on decomposition of have training data which consists of similarly segmented artificially combined biblical books [4], [17]. This work is code samples by our suspect programmers, rather than full relatednotonlytoourfuturegoalofperformingsourcecode files. Note that this later assumption does not particularly segmentation, but also in terms of scale of classification. limit us in practical application because we can artificially In their technique, they cluster chunks and then classify segment a single authored file if necessary. sentences, with a processing step using stronger classifi- In our primary case, we assume that our segmented cations to adjust weaker classifications. Since we assume samples are linked by the segmentation method. Through we already have segmentation, our work is most related to version control methods this would correspond to accounts, theclassificationstep.Weclassifysmallsegmentsofsource whilethroughothermethodsthismaycorrespondtoclusters code and then use other segments to improve our accuracy. generated through a clustering algorithm. We refer to this However, their technique for supporting classification is a caseasmultiplesampleattributionorasaccountattribution. sequential gap-filling technique while we aggregate classi- fication predictions. Formally,wehaveasetofsourcecodesamplesDwhich Another segmentation technique is a sliding window waswrittenbyanunknownauthorAandasetofnsuspects technique to divide a document into sections by individual A1...An,andforeachsuspectAi wehaveasetofsamples authorsproposedbyFifieldetal.[11].Thistechniquerelies Di. We then want to correctly attribute D to an Ai. Where on multiple clustering passes over the text, where each not otherwise stated, we assume the closed world, in which clustered document is of reasonable length. Our individual one of the n suspects is the true author. pieces are on a smaller scale than theirs, and we do not While we believe that most forms of segmentation nat- needtoperformmultipleevaluationspersampletoattribute urally lead to linking, we acknowledge that by presenting them.Wementionthisworkbecausethegoaloftheworkis a technique based on linking we may create the assump- related to ours, even though the technique is very different. tion that to defend against it one only needs to contribute Because we are interested in the open world problem, in a way which cannot be linked, such as through guest wehadtolookbeyondthoseworkstotheworkofStolerman “accounts” or throwaway accounts. Therefore, we not only et al. [26]. They introduce a method called Classify-Verify evaluate the baseline where the cardinallity of our code which augments classification with verification. Authorship sample sets is always 1, but also present ways analysts can verification is the problem of determining if a document D interpret the results to compensate for the lower accuracy. waswrittenbyanauthorA.Amongtheverificationmethods We refer to this scenario as single sample attribution. Figure1.Thissummarizesourmethodforauthorshipattributionofpartialsourcecodesamples. 3.2. Data Preparation TABLE1.SAMPLEOFCORPUSSTATISTICS LinesofCode(LOC) NumberofSamples Percentage We collected data from public C++ repositories on 1 3125 54.11% GitHub. We collected repositories which list C++ as the 2 954 16.52% primary language, starting from 14 seed contributors and 3 457 7.91% spidering through their collaborators. Doing this, we col- 4 262 4.54% lected data from 1649 repositories and 1178 programmers, 5 169 2.93% although in future processing steps we found that many of 6 105 1.82% these programmers and repositories had insufficient data. 7 94 1.63% 8 71 1.23% Additionally, some of these programmers were renames or 9 59 1.02% group accounts, while some repositories included text other 10-99 445 7.71% than C++ code which had to be discounted. After eliminat- 100-554 34 0.59% ing those and setting the threshold to at least 150 samples perauthorwithatleast1lineofactualcode(notwhitespace orcomments),wewereleftwith106programmers.Wenote which introduce complications in data extraction. Secondly, thatthisthresholdwaschosenwithanexperimentalmindset gathering data from git blame is faster when attempting to to ensure that we had sufficient data for both training and determine authorship of parts of chosen files, while collect- testing sets. ing commits would be faster for attempting to determine We then used git blame on each line of code, and for the authorship of an individual account. Thirdly, we believe each set of consecutive lines blamed to the same program- the results of git blame are closer to the results we would mer we encapsulated those lines in a dummy main function achieve if we were to use some technique to segment code andextractedfeaturesfromtheabstractsyntaxtreeasin[9]. which is not version controlled on a publicly accessible However, unlike in [9] we cannot use information gain to repositiory. prune the feature set due to having extremely sparse feature We took the 15 programmer dataset and extracted de- vectors and therefore very few features with individual tailed corpus statistics. Table 1 shows the count and per- information gain. centage of samples with various numbers of lines of code, We then removed all samples which occured multiple excludingthe dummymainframing. Wenotethat whilethe timesandprunedthedatasettoanequalnumberofsamples large samples are of similar size to some full files, none of per author. Our overall dataset included 106 programmers, the samples are complete files, and that half of the samples each with at least 150 samples. For some experiments we withover100linesofcodebelongtothesameprogrammer. also used a smaller dataset with 15 programmers with 385 samples each, from which we also used subsets with 150 3.3. Features samples each and 250 samples each. We then constructed specific subsets of the 106 author In this work we use a feature set derived from the work dataset. The first such dataset contains 90 samples of at ofCaliskan-Islametal.[9].Ourprimaryfeaturescomefrom least 3 lines of code each for 96 programmers. The other theabstractsyntaxtreeandincludenodesandnodebigrams contains 90 programmers with variation in the number of [3].Theabstractsyntaxtree,orAST,isatreerepresentation samples and minimum lines of code, and will be discussed of source code with nodes representing syntactic constructs in more detail in the results section. in the code, and we used the fuzzy parser joern to extract While we acknowledge that the ground truth for git them[28].ThisparsingallowsgeneratingtheASTwithouta blame is weaker than for commits, we chose to use git completebuildandwithoutthecompletebuildenvironment. blame for three primary reasons. Firstly, commits can in- Thus, it allows us to extract the AST even for our partial clude deletions and syntactically invalid constructs, both of codesamples.Wealsoincludewordunigrams,apisymbols, andkeywords.OurfeaturesetincludesbothrawandTFIDF and we ensured that product of the two was always either versions of many of our features. TFIDF is a measure the total number of samples per author or a divisor of it. combining the raw frequency with a measure of how many Our first method is sample merging. For this, we added authors use the feature. Due to the sparsity of the feature the feature vectors of samples together. We tried merging set, we do not use information gain to prune the set, and both in the extracted (alphabetical by sample name) order insteadkeeptheentirefeatureset,minusanyfeatureswhich and in random order. By merging in the extracted order, are constant across all samples [24]. Information gain is we maintain code locality, while merging in the random an entropy based measure of the usefullness of a feature order spread code throughout merged groups. We refer to for spliting data into classes by itself, and because of the mergingmaintaininglocalityasorderedmergeandmerging sparsity of our feature vectors is zero for most features. dispersing locality as random merge. For this method we For the 15 programmer dataset, we have 62,561 features, used three experimental setups. In the first, we combined of which for any given sample an average of 62,471 are samples in both our known training set and our testing set. zero-valued, and the 106 programmer dataset has 451,368 In the second, we only combined our training samples, and features. in the third we only combined our testing samples. Our second proposed method is also our preferred method. This method does not involve any adjustment to 3.4. Single Sample Attribution the feature vectors. Instead, it requires performing the same classification as for single samples but then aggregating For this case, we assume that we have no information results for the samples that we would have merged by our about the authorship of the samples we are attempting to other methods. We aggregate the probability distribution classify. As a use case, we can imagine the case where the outputoftheclassifierratherthanthepredictedclasses,and sample is git blamed to an anonymous user rather than to then take as the prediction for the aggregated samples the an account, or when a cautious individual is creating a new class with the highest averaged probability. account for every commit. Therefore, we can only classify at the level of the individual sample. For this, we perform 3.6. The Open World cross-validation with random forests, as in [9]. Random forests are ensemble multi-class classifiers which combine For the open world, we propose a variation of the multiple decision trees which vote on which class to assign calibration curves described in Section 3.4. We perform to an instance [5]. This serves as a baseline for our work. attribution as normal according to either single sample at- Ideally, we would then continue as in Section 3.5 for tribution or account attribution, and our goal is to use a multiple sample attribution. However, in the event that we threshold to separate samples by unknown authors which cannot,weapplyatechniquetohelpanalystsbetterinterpret were attributed to a suspect due to the mechanics of the the results. Because we suspect that some samples will classifier from samples correctly attributed to one of our remain which are difficult if not impossible to classify, we suspects. want to know at what level of confidence, or the output For the purposes of our experimentation, we used our probabilityfortheselectedclass,wecanacceptaprediction. 15 programmer dataset. We performed an initial proof-of- Therefore, we create a calibration curve for our classifier. concept experiment using a small set of unknown authored We bin the samples based on the highest classifier proba- samples and 250 samples of training data per known pro- bility output in increments of 10%, and report the accuracy grammer. Following that, we performed experiments in the for samples in each interval. For random forests, the output following way. We divided our 15 programmer dataset into probabilities refer to the percentage of trees which vote for three disjoint subsets of five programmers. We performed the given class. While we acknowledge that the specifics threeroundsofexperiments,andforeachroundwetookone of such a curve may vary for different instances of the of the subsets as the set of unknown authors U. Then we problem and we recommend using cross-validation with performed 11-fold cross-validation on the remaining data, known samples to prepare such a curve in order to identify adding all of documents from U to the evaluation set. We a threshold for accepting a prediction based on the stakes, then binned the samples as in our calibration curves, with we expect that the overall shape of the calibration curve eachbinmaintainingcountsofcorrectattributions,incorrect will remain similar for different datasets, and so ours can attributions of samples belonging to authors not in U, and be used as a guide. samples belonging to authors in U, which we refer to as being“outofworld”.Wenotethatdevisingourexperiments 3.5. Multiple Sample Attribution in this way allowed us to heavily bias our evaluation set in favor of samples by programmers outside of our suspect Forthiscase,weassumethatwewereabletogroupthe set, analyzing 317,625 out of world samples and 57750 “in samples as in an account and want to identify the owner. world” samples between all rounds. Therefore, we can leverage the groupof samples to identify Wethenevaluatedthresholdsatthelowerboundofeach theauthorofallofthem.Weidentifiedtwomainwaystodo binintermsofprecisionandrecall,butratherthancalculate this. These experiments have as parameters the number of the precision and recall of the classifier itself we computed combinedsamplesandthenumberofcross-validationfolds, precision and recall with respect to the three classification counts maintained by the bins, using the threshold as the 3.9. Ground Truth Considerations selector.Precisionisameasureofthepercentageofselected instances which belong to the desired category while recall We acknowledge that ground truth in the GitHub envi- is a measure of the percentage of instances belonging to ronment is not perfect. First, we know that it is possible the desired category which were selected. We calculated that code is copied from other sources, and therefore is not precisionandrecallaccordingtothefollowingthreecriteria: theoriginalcontributionofthecreditedauthor.Furthermore, correct classifications above the threshold, out of world using git blame at the line level indicates the last author to samples below the threshold, and samples which are either touch the line, not the original author of all of the parts out of world or classified incorrectly below the threshold. of the line. We note that despite the inherent “messiness” For real world applications, we suggest using a similar of the data, it is important to evaluate on data collected approach prior to introducing the actual samples of inter- from the wild which well reflects realistic application of est. We then suggest setting a threshold based on these our techniques. Therefore, we devised an experiment to try values and the needs of the application. For the purposes to quantify the contribution of inaccurate ground truth. of this paper, however, we calculate the F1 score for each For this experiment, we perform cross validation on of the three criteria and use this to predict what may be Google Code Jam data as is used by [9] with 250 authors useful thresholds, and to evaluate the power of the tech- and 9 files each. We then set a parameter m for number of nique. F1 scores are calculated according to the formula ground truth corruptions to perform. Each corruption is an 2 ∗ (precision ∗ recall)/(precision + recall), and are a author swap between two files. We use Google Code Jam harmonic average of the two values. data because it gives us more reliable ground truth, and so we can control for the quality of the ground truth, while if we had used GitHub data we would not know the amount 3.7. Dataset Size Factors of corruption already present. The results are described in Section 4.6. It is well established that the amount of training data available and the number of suspects have an important 4. Results effect on classification accuracy. In our problem, we have two ways of varying the amount of training data available. Onewayistovarytheminimumnumberoflinesofcodeper 4.1. Single Sample Attribution sample,andtheotheristovarythenumberofsamplesused per programmer. To observe these effects, we performed From the 106 programmer dataset, our baseline single single sample attribution on numerous different subsets of sampleattributionaccuracywas73%for500trees.Wenote our larger dataset, obtained via stratified random sampling thatwhilethisismuchlowerthantheaccuraciesreportedby byauthor,andexperimentedwithdifferentlevelsofmerging [9],thedataitselfisverydifferent.Theworkof[9]attributes for given subsets. whole source code files written privately with an average of To furhter examine the effects of dataset size, we took 70 lines of code per file, while our work attributes pieces the 15 author dataset and limited to only samples which are of files written publicly and collaboratively with an average one line of code long. We then vary the number of samples of 4.9 lines of code per file. Intuitively, it is reasonable to per author from 10 to 130 in increments of 10 and use 10- believe that our dataset contains samples which are much fold cross-validation. harder to classify than those found in previous datasets. Figure 2 shows the calibration curve constructed from this experiment. The calibration curve shows that our clas- 3.8. Special Case Attribution Tasks sifierisconservative:thepredictedprobabilityislowerthan the actual accuracy obtained (a known feature of random Inadditiontothestandardattributiontask,sometimeswe forests). Even when the classifier confidence is less than want to solve special cases. In particular, we consider the 10% we still do better than random chance. More interest- two tasks. The first task is a two-class attribution scenario, ingly, it shows that with even 40% classifier confidence we in which we have two people who claim authorship and have nearly 90% accuracy and with 50% classifier confi- we want to determine which wrote the code. The other task dencewehavenearly95%accuracyamongsampleswithat is verification, in which we have one suspect and want to least that confidence. Thus, depending on the consequences know whether or not that person wrote the code. For both ofbeingwrong,wecouldchooseanappropriatebound,such of these, we use our 15 programmer dataset. For the two- as 40% or 50%, as the classification confidence threshold. classscenario,wecheckeachpairofprogrammersforsingle While this will cause us to lose correct classifications, in sampleattribution.Forverification,foreachprogrammerwe real settings false negatives are often less harmful than create another “author” from samples from the remaining false positives, and the attributions of samples below the 14. We then perform a two-class single sample attribution thresholdcanstillbeusefulinguidingfurtherinvestigation. classification task between the single author and the col- Furthermore, even if we cannot accept an attribution due to lected other 14. For both experiments, we used 11-fold low confidence, it still gives us a starting point for further cross-validation. investigation. each confidence interval for both data sets. Figure 4 shows thepercentagesofsampleswhichfallineachinterval.From this, we see that for the 106 programmer dataset, most of the samples fall in the lower confidence intervals, which explainswhyouraccuracyisonly73%whilemostintervals haveaccuracyover90%.Forthe15programmerdatasetwe can see that the curve is biased in favor of samples in the range of 10% to 30% confidence, which explains the fact that although most of the intervals have high accuracy our overallaccuracyisonly69%.Wenotethattheintervalfrom 0% confidence to 10% confidence does not actually contain 0 samples, but has less than 0.1% of the samples. Figure2.Thiscalibrationcurvecomparesaccuracybasedontheconfidence leveloftheclassifiertorandomchanceforsinglesampleattribution.The x-axis shows the probability level for the predicted class as output by the classifier, divided into bins of 10%. The y-axis shows how often the predictedclasswascorrectfortheinstanceswiththatprobability. With the 15 programmer dataset we performed cross- validation with 5, 7, 11, 35, 55, and 77 folds, and our baseline results ranged from 70% accuracy for 5 folds and 71% accuracy for 77 folds. Because of this limited variability, we conclude that the number of folds is not particularly important for single sample attribution as long as we maintain sufficient training data. Figure4.Thisgraphshowsthepercentagesofthesamplesthatfallineach of the confidence intervals for the calibration curves in Figures 2 and 3. Wenotethatforthe15programmerdatasettheintervalfrom0%to10% confidencecontains0.06%ofthesamples,notactually0%. Our calibration analysis suggests that our low overall accuracy compared to previous results on full source code files from Google Code Jam is likely in part a result of our dataset containing data which is difficult to classify. Detailed manual analysis would be required to determine if the data is difficult to classify because it is trivial, copied from somewhere else, or mislabeled due to reliance on git blame for ground truth. We performed a preliminary analysis, and we noticed some characterstics shared by many, although not all, of the misclassificatons. Many of the misclassified samples Figure3.Thiscalibrationcurvecomparesaccuracybasedontheconfidence were trivial, and contained only very basic programming leveloftheclassifiertorandomchanceforsinglesampleattribution.The structures. The majority of the misclassified instances had x-axisshowstheprobabilitylevelforthepredictedclassasoutputbythe only a few abstract syntax tree nodes per line of code, with classifier, divided into intervals of 10%. The y-axis shows how often the predictedclasswascorrectfortheinstanceswiththatprobability. many of the longer samples averaging less than one node per line of code. 57.4% of the misclassified samples had Figure 3 shows a calibration curve created with the only 1 line of code, and 43.4% of the of the samples with 15 programmer dataset and 11 fold cross-validation. On only1lineofcodeweremisclassified.Theaveragelengthof this run, our overall accuracy was 69%. This calibration misclassified samples was 3.7 lines of code, while correctly curve was similar to the calibration curve generated from classified samples were 5.7 lines of code long on average. the 106 programmer dataset, suggesting that calibration Thismeansthatmanyofourmisclassifiedsampleshaveonly curves for different problems will be similar. Therefore, we afewabstractsyntaxtreenodesandmostoftheinformation can make general recommendations to use either 40% or comes from the specific word unigrams which make up the 50% confidence as a threshold to protect against negative code. As we know from [9], word unigrams provide less consequences of mis-attribution. information than abstract syntax tree nodes. Therefore, it is We also counted the number of samples which fell into to be expected that samples for which most of the already TABLE2.RESULTSFOR150FILE15AUTHOREXPERIMENTS authorship attribution, and is the reason most experiments conductedunderlaboratoryconditionsrequirethatprogram- Experiment Ordered Random mers have the same set of functionalities in the code. Combination Accuracy Accuracy From these aggregation results, we conclude that the TrainonIndividual, 58.1% 60.3% quality of the grouping of samples is important to the ClassifyAveraged TrainonAveraged, 28.5% 20.8% accuracy improvement, and that while merging samples is ClassifyIndividual effective it is better to keep the variation in the training sets TrainonIndividual, 80.0% 80.0% andonlycombinetheclassificationsamplesafterperforming ClassifyIndividual classification. We also notice that all of the accuracies are TrainonAveraged, 98.0% 98.0% ClassifyAveraged betterthanthebaselineaccuracyforsinglesampleclassifica- tion.Therefore,werecommendusingthestrategyoftraining on small samples from the suspects and then using the small amount of information comes from word unigrams classificationaggregationstrategyonthesamplesbelonging rather than from abstract syntax tree nodes would prove to the same account. This is the strategy we continue to use more difficult to classify. for the remaining experiments. The calibration curve also suggests why we do so well with our classification result aggregation. Because our clas- sifier is so conservative, our misclassificatons tend to have very even spreads of low probabilities compared to our correct classifications, which means that they do not easily outweigh the probabilities of correctly classified instances. This leads to the whole group being correctly classified. 4.2. Multiple Sample Attribution For speed of experiments, we started with our 15 pro- grammer dataset and then repeated the most successful experiment with our larger datasets. First we used our 15 programmer dataset and attempted attributionbetweenmergedsamplesandindividualsamples. For these experiments, we kept 15 samples per programmer Figure5.Thesearetheresultsformergingsamplesinour15programmer as individual samples and merged the rest into 9 merged dataset. We show the results from ordered merge, random merge, and samples of 15 samples each. Because we were comparing classificationresultaggregation. with individual samples, when we merged samples we nor- malized them by averaging features rather than adding. Figure 6 shows the results of varying the number of Table 2 shows the results of this experiment. These training samples and aggregated result classification sam- resultsshowthataveragingbothtrainingandtestingsamples ples. These results show that accuracies of about 90% can is best, and that averaging either the training samples or the be obtained with a minimum of about 10 training samples testsampleswithoutaveragingtheotherworsenstheresults. if there are at least about 50 aggregated samples. However, Figure 5 shows the accuracies for our 15 programmer usingmorethan60trainingsampleshasdramaticallydimin- dataset using the various merging methods. Merging in ishing returns, and aggregating more than about 20 samples order yields some improvement over classifying individual also has dramatically diminishing returns. We see that hav- samples, but our accuracy is greatly improved by merging ing a minimal number of training samples is essential, but randomly.Butthebesttechniqueistocombineclassification oncewepassthatwecanimproveaccuracyeitherbyadding results rather than samples. However, we note that merging moretrainingsamplesor byaggregatingmoreclassification the samples is faster than aggregating the results and has results. lower memory requirements, so at large scale might be Becauseweconcludedthataggregatingtheclassification preferable. resultsissuperiortomergingsamples,wefocusedonresult We note that a large source of the difference between aggregationforlargerscaleexperiments.Figure7showsthe ordered merging and random merging is the locality of results for varying numbers of aggregated results from our code samples, and that in this respect aggregation is more 96programmerdataset.Wenotetwoimportantobservations. like random merging. On one hand, reducing locality with First, even aggregating the results of two classifications random merging could cause some functionality specific gives us a dramatic increase of accuracy, allowing us to go code to be spread across merged samples and inflate our from75%accuracyto95%accuracy.Second,increasingthe accuracy,butontheotherhandbetterspreadingthesamples numberofaggregatedresultsgivesaboostinaccuracywith meansthateachcollectionofsamplesismorerepresentative diminishing returns as the number of samples increases. oftheoverallstyle.Furthermore,functionalityspecificcode Figure 8 shows the results for varying numbers of ag- is an acknowledged problem in researching source code gregated results from our 106 programmer dataset. Classi- experiment. We obtain classification results within a few minutes with these settings which result in 38% accuracy. In this experiment, we observe that averaging classification probabilitydistributionsimprovesclassificationsignificantly evenwhenusingasuboptimalclassifier.Averagingonlytwo classification distributions increases accuracy from 38% to 77%. Furthermore, by aggregating 50 samples we are still able to achieve 99% accuracy. Figure6.Thisgraphshowsthechangeinaccuracyaswevarythenumber oftraininginstancesandthenumberofaggregatedclassificationsamples, with the units on both axes representing the number of samples. From thisgraph,wecanseethatweneedaminimumof10trainingsamplesto gethighaccuracy,butwegetbooststoaccuracybyaddingmoretraining samples up to about 60 samples. We also see that with enough training samples,wecangethighaccuracywithatleast5aggregatedsamples,but with fewer training samples we get boosts to accuracy by adding up to about20aggregatedsamples. Figure 8. These are the results for aggregating classification results in our 106 programmer dataset with the 500 tree classifier. We show the resultsrangingfromsinglesample attribution toaggregatingonethirdof thesamples. Figure7.Thesearetheresultsforaggregatingclassificationresultsinour 96 programmer dataset. We show the results ranging from single sample attributiontoaggregatinghalfofthesamples. Figure9.Thesearetheresultsforaggregatingclassificationresultsinour 106 programmer dataset with the 50 tree classifier. We show the results ranging from single sample attribution to aggregating one third of the fication with our standard parameters including 500 trees samples. in the random forest with unlimited depth and using all available training data takes approximately 20 hours on a 32 core 240GB RAM machine. Here we see that we can 4.3. The Open World get 70% accuracy for single sample attribution and reach 95% accuracy for pairs of samples and 99% accuracy for Figure 10 shows the results of our initial open world sets of 15 samples. experiment. In this experiment, we used the 15 program- In order to perform a faster classification on this large mer dataset as our suspects and trained a model on these dataset, we also trained a random forest with parameters programmers. We then tested this model on the remaining that are known to result in lower accuracies. For exam- programmersinourlargerdatasettosimulateanopenworld ple, the number of trees is 50 with a maximum allowed experiment. Our results suggest that the calibration curve depth of 50, while using 50% of the folds for training method is a viable way to address the open world problem. instead of 100%. Figure 9 shows the results from this Wenoticethatforourdataset,sampleswhichdonotbelong to the suspect set usually have classification confidence likelyeither60%or70%confidence.At60%confidence,we below 20% and the highest such confidence is 23%, while have an F1 score of .503 for correctly attributed instances most incorrect classifications occur with confidence below above the threshold, with higher precision than recall. At 40%. Because we have a similar calibration curve for 106 70% confidence we have F1 score of .927 for out of world programmers,weexpectthatwewouldhavesimilarlyuseful samples below the threshold and .958 for either out of thresholds for that expanded dataset as well as for other world or incorrectly attributed samples below the threshold, datasets. with recall higher than precision for both measures. As we We also notice that the percentiles tend to match up increase the threshold the precision for correct attributions with each other between classification results. For example, risessharplybecauseastheconfidenceincreasesitbecomes we observe that the best 75% of the correct classifications much more likely that the attribution was correct. However, have confidence greater than the worst 75% of incorrect the recall for correct attributions falls sharply because we classifications. We also see that the best 50% of the correct have many samples which are attributed with low confi- classifications have confidence greater than all but the out- dence, and once we reach about 30% confidence we start liersamongtheincorrectclassifications.Ourresultssuggest having many correct attributions among them. For the out that misclassificatons due to the open world scenario are of world and incorrect samples, we notice that precision is similar to general misclassificatons with respect to classifi- consistently high but falls slowly. When combined with the cation confidence with an even lower confidence threshold factthattherecallrisessharplyearlybeforelevelingoff,this and that an open world can be handled by discarding such suggests that we quickly identify the majority of the out of low confidence predictions, which we would likely already world and incorrect samples while discarding relatively few discard or handle skeptically based on our calibration curve correctly attributed samples, and so once we go beyond a (see Figure 3). However, our remaining experiments show threshold of about 40% confidence we are mostly losing that this is likely a quirk of the specific match of supsects correct attributions and not identifying out of world or authors and unknown authors. incorrect attributions. Taken together, this reinforces what wenoticedpreviouslyinFigure10:correctattributionshave a different, although overlapping, confidence distribution from incorrect attributions and out of world samples. Figure10.Thischartshowstheclassifierconfidenceincorrectclassifica- tionsandmisclassificationsinaclosedworldscenarioandalsoclassifica- tionconfidenceforsamplesthatdonotbelongtoanyoftheclassesinthe trained model from 15 programmers with 250 samples each. The x-asis labels also include the number of samples which belong to each group. Figure11.Thisfigureshowstheprecisionandrecallvaluesforouropen We note that confidence from samples by authors outside the supect set worldexperimentsforsinglesampleattribution.At60%confidence,which havelowerconfidencethanmisclassifiedsamplesfromwithinthesuspect hastheoptimalF1scorewithrespecttocorrectlyattributedinstancesabove set.Themaximumconfidenceforsamplesoutsidethesuspectsetwas23% thethreshold,theprecisionis.610andtherecallis.428withrespecttothat andthemaximumconfidenceformisclassificatonsfrominsidethesuspect measure.At70%confidence,whichhastheoptimalF1scorewithrespect setwas75%;howeverinbothcasesthesemaximumvaluesarestatistical totheothertwomeasures,outofworldprecisionandrecallare.872and outliers. .989respectivelywhileoutofworldorincorrectattributionprecisionand recallare.930and.989respectively. Figure 11 shows the results of our open world ex- periments using 10 suspect programmers and 5 unknown Figure 12 show the results of our open world ex- programmers for the single sample attribution case. We periments with 10 suspect programmers and 5 unknown note that the overall accuracy, ignoring the out of world programmers for the multiple sample attribution case for samples, is 68.3%. While we consider selecting a threshold collections of 7 samples. We note that the overall accuracy, to be application specific because both the importance and ignoringtheoutofworldsamples,is98.0%.TheoptimalF1 values of the precision and recall measures may vary, when score for correctly attributed instances above the threshold we calculated the F1 scores we determined that, depending is 30%, with F1 score of .691 respectively. The optimal F1 on whether identifying correctly predicted samples or out scorefortheothertwomeasuresisforthethresholdof40%. of world samples is more important, the ideal threshold is For collections of 7 samples, those optimal scores are .941