LiDetector: License Incompatibility Detection for Open Source Software

Since license texts are typically long and complicated, it is not easy to directly interpret license texts. For each license, LiDetector first identifies named entities of license terms which state the conditions of software use. In this paper, a named entity refers to a specific expression of a license term shown in Table 1, which can be a word, a phrase, or a sentence. Inspired by Named Entity Recognition (NER) (Fan et al., 2020; Guo et al., 2021a, b) in natural language processing, this paper utilizes sequence labeling to identify and localize license term entities. Before sequence labeling, LiDetector first splits each license text into sentences by Stanford CoreNLP (Group, 2020), an integrated framework for natural language processing. After that, we employ the BIO (Begin, Inside, and Outside) mode (Reimers and Gurevych, 2017) to label each token in a sentence. As illustrated in Fig. 4, B-X implies that the current token is at the beginning of a named entity of the $X^{th}$ license term in Table 1. For instance, B-0 in Fig. 4 implies that distribute is the beginning token of a named entity whose license term is the first one in Table 1. Similarly, I-X implies that the current token is inside a named entity of the $X^{th}$ license term, and O represents a token outside name entities. In the training phase, we manually tag each sentence by the BIO mode, and obtain a training dataset for sequence labelling of license sentences. In the inference phase, LiDetector automatically predicts the labels of tokens in license texts, so as to identify and localize license term entities.

Based on the tagged dataset, we train a probabilistic model to predict the label of each token in a license text. As illustrated in Fig. 5, the model consists of three parts: word embedding, sentence representation, and probability calibration. (1) Word embedding. To serve as the input of the model, we first embed words in license sentences into vectors. Since licenses are expressed by natural language, we exploit prior knowledge on word semantics and employ the pre-trained Glove model (Richard Socher, 2014) for word embedding. (2) Sentence representation. To represent each sentence in the license text, we feed the results of word embeddings into a bi-Directional Long Short-Term Memory (bi-LSTM) (Xia et al., 2019) model, and learn the representation of each license sentence. (3) Probability calibration. Given a token and its context vector learned by bi-LSTM, the model then calibrates its probability distribution over each category (label) by Conditional Random Fields (CRF) (Andow et al., 2019), so that the contextual information represented by the hidden layer state can be utilized to make a global decision. To reduce the labelling effort and enhance performance, we implement the probabilistic model by semi-supervised training. Specifically, after training with labelled samples, we used the trained model to predict license terms for unlabeled samples. Then, all samples, including labelled samples and other samples with pseudo labels, were collected to train the model. The rationale behind is that pseudo labelling of unlabelled samples are also predictive. Finally, the output of the probabilistic model is a sequence of labels from where license term entities can be directly inferred.

For instance, given the first running example in Section 2.4, the label sequence of the sentence “Redistribution and use in source and binary forms, with or without modification, are permitted” predicted by the probabilistic model is {B-0, I-0, I-0, I-0, I-0, I-0, I-0, I-0, O, O, O, O, O, O}. By this means, LiDetector can localize the license term entity “redistribution and use in source and binary forms”, and identify the license term “Distribute” from the sentence.

To infer the conveyed attitudes towards identified license terms, we first conduct grammatical analysis on the sentences where term entities are localized. Since license texts are expressed by natural language under universe grammar rules, we exploited the pretrained Probabilistic Context-Free Grammar (PCFG) model (Scicluna, 2016) from Standford CoreNLP (Group, 2020) to assign a probability to each grammar rule. By this means, a syntax tree can be obtained by selecting the tree with the highest probability scores. Fig. 6 displays an example of grammar parsing on the sentence “You can not refuse such a promise that significant changes must be declared” from CC-BY-SA-4.0 (SPDX, 2018c). In this case, “significant changes must be declared” is an identified term entity, which refers to a license term “State Changes” (No.15 in Table 1). In Fig. 6, non-terminal nodes such as NP and VB represent the part-of-speech tags (Ling, 2003), and a leaf node such as refuse and changes represents a token in the license sentence. Table 2 shows the part-of-speech tags associated with their descriptions. By traversing the grammar tree, we can obtain the full path of each leaf node, which is the grammatical sequence of the token in the parsed sentence. For example, from Fig. 6 we can acquire the path from the ROOT node to the leaf node refuse as $ROOT\rightarrow S\rightarrow VP\rightarrow VP\rightarrow VB\rightarrow\textit{refuse}$. It indicates that refuse is a verb in the verb phrase “refuse such a promise that significant changes must be declared” (denoted by $V_{1}$), which is dominated by can and not, two tokens in a larger verb phase that contains $V_{1}$. Taking Fig. 2a as an example, it can be inferred that the license term entity “redistribution and use in source and binary forms” is a noun phrase (NP) in the sentence, and the attitude towards this license term is affected by the verb phrase (VP) “are permitted”.

Based on the results of license term identification and grammar parsing, we perform sentiment analysis to infer the attitudes towards these terms. Generally, the attitudes towards license terms can be categorized into three types, i.e., MUST, CANNOT, and CAN. Given a target sentence $l$ and a license term $k$ identified from the sentence, LiDetector infers the attitude towards $k$ via sentiment analysis. When the attitudes towards all identified terms are inferred, LiDetector obtains a summary of rights and obligations of the whole license, i.e., $T(l)=[t_{0},t_{1},...,t_{22}]$, where $t_{i}$ represents the attitude towards the $i^{th}$ term in Table 1, $t_{i}\in\{\text{CAN, CANNOT, MUST, UNKNOWN}\}$, and $0\leq i\leq 22$. Note that absent license terms are marked with UNKNOWN. Specifically, we first define a set of parts of speech that may convey permissive or restrictive attitudes of authors, i.e., Verb (VB, VBD, VBG, VBN, VBP, VBZ) and Others (MD, IN, RB, RBR, RBS). Tokens with these parts of speech are regarded as powerful tokens (PTs).

For instance, the token you in Fig. 6 is not a powerful token since its part of speech is RPR, which is supposed to have no influence on the attitudes. After obtaining all PTs, we further divide them into two groups according to their relationships with the target entity.

• •

  Internal PTs: An internal PT represents a token contained in the target entity. Typically, internal PTs directly declare the rights and obligations towards the target license term. For example, in Fig. 6, the tokens must, be, and declared are three internal PTs of the entity significant changes made to software must be declared within the copies.

• •

  External PTs: As a part of a sentence, the sentiment analysis towards the attitudes needs to consider external PTs which are outside the target entity but have a dominant influence on the attitude towards the target entity. For example, in Fig. 6, tokens such as can, not, and refuse are three external PTs that dominates the attitude of the entire sentence.

Given a license term entity, we first collect its internal PTs that directly declare the rights and obligations. Then, based on the parsing results, we search for the external PTs that may dominate the attitudes towards the target entity. By this means, we can acquire a set of PTs that are further used to infer the rights and obligations implied by licenses. Since the expressions of attitudes are not as flexible as those of license terms, we define a set of words and phrases in Table 3 as the expressions of each attitude. Finally, for each PT, we apply a heuristic strategy to infer the attitudes. Specifically, we mark a PT with CANNOT or MUST if it belongs to the corresponding expressions listed in Table 3; otherwise, we mark it with CAN. Double CANNOT is offset.

We note that for right-related terms, as previous studies (choosealicense, 2012), the absence of them are marked with CANNOT since no rights are explicitly granted in the license; while for obligation-related terms, the absence of them are marked with CAN. In this way, we can infer the attitude towards each license term. For example, in Fig. 2a, there are no internal PTs in the license term entity “redistribution and use in source and binary forms”, and the external PTs are {“are”, “permitted”}. According to Table 3, LiDetector infers the attitude towards the license term “Distribute” as CAN, and thus the right conveyed by the project license is “CAN Distribute”.

After identifying license terms and the attitudes towards them, rights and obligations related to each term can be inferred (e.g., CANNOT Redistribute). Although we treat each license term independently in the previous steps, license terms can also be the conditions of other terms. For instance, “you can modify if you state changes”. In this case, there are two license terms (i.e., “Modify” and “State Changes”), and the right (i.e., “Modify”) is only granted under certain constraint (i.e., “State Changes”). To address this issue, we analyze the condition relationships between license terms. Specifically, based on the parsing results, we identify the conditional clauses that state the conditions of software use. License terms in the conditional clauses are the conditions of terms in the main clause. Finally, we separately assume the condition is satisfied or not, and update the attitudes of license terms in both conditional and main clause. We describe incompatibility analysis when faced with conditions in Section 3.5.

The evaluation was conducted in three phases (i.e., license term identification, right and obligation inference, and the overall incompatibility detection). In the first two phases, LiDetector performed tagging, training, and testing in sentences. Specifically, we collected the license sentences from two sources: (1) tldrlegal (kevin, 2012), a platform where licenses can be uploaded, summarized, and managed by users. We collected license sentences accompanied with license term tags (i.e., CAN, CANNOT, and MUST), and obtained 11,973 labeled sentences from 212 labelled licenses on tldrlegal. (2) Github. We crawled 1,846 popular projects with more than 1,000 stars and extracted licenses from them. Then, we filtered out duplicated licenses and finally obtained 48,275 sentences from GitHub. Then, we randomly selected 9,871 sentences (i.e., 20%) to carefully label, and the remaining 38,404 sentences from 754 unlabelled licenses were fed into the semi-supervised learning to enhance the performance of identifying license terms. In total, we obtained 21,844 labeled sentences (i.e., 11,973 from tldrlegal and 9,871 from Github). We randomly split these samples into the training and testing datasets by 4:1, and further split the training dataset for training and validation by 4:1. Therefore, in the first two phases, the training, validation, and testing dataset consists of 13,980, 3,495, and 4,369 license sentences. Three authors cross-validated the labels and a lawyer from Yingke Law Firm¹¹1www.yingkeinternational.com was involved in the validation. All the techniques and tools were evaluated on the same testing dataset. We have made the dataset publicly available (Xu et al., 2021a).

To save the manual efforts of labelling licenses, we employ a semi-supervised learning method to identify license terms, so that both labelled and unlabelled licenses can be utilized to train the probabilistic model. The rationale behind is that pseudo labels predicted by the model are also predictive and may benefit the model performance when involved in training. Before evaluating the performance of LiDetector, we first investigate how the number of unlabelled samples influences the performance of LiDetector. Specifically, we randomly select a set of numbers of licenses (i.e., 100, 200, 300, 400, 500, 600, 700) from the 754 unlabelled licenses, extract the sentences, and add them into the training dataset respectively. We use three metrics to evaluate the performance of LiDetector, i.e., precision ($P=\frac{TP}{TP+FP}$), recall ($R=\frac{TP}{TP+FN}$), and F1 score ($F1=\frac{2*P*R}{P+R}$). To avoid bias, for each parameter, we randomly select the same number of unlabelled licenses for three times, and average the results. Fig. 7 shows the performances of LiDetector accompanied with different sizes of unlabelled licenses. It can be observed that the performance of LiDetector peaked when 300 unlabeled licenses were added for semi-supervised training. In the Fig. 7, it can be observed that when more unlabeled data were involved in the semi-supervised training, the performance of LiDetector first increased and reached a peak when the size of unlabeled data is 300. It is consistent with the hypothesis that pseudo labels are predicted for the unlabeled data. However, when the size of unlabeled data is larger than 300, the performance of LiDetector decreased. A possible reason could be that pseudo labels might introduce some noisy data, which prohibited the enhancement of model performance. Therefore, to achieve the best performance, we decide to add 300 unlabeled licenses (i.e., 15,312 sentences) into the training dataset for our semi-supervised learning phase in LiDetector in the following experiments. All experiments were conducted on a machine with Intel (R) Core (TM) i5-7200U CPU @ 2.70 GHz and 4.00 GB RAM.

To evaluate the ability of LiDetector to identify license terms, we compare it with FOSS-LTE (Kapitsaki and Paschalides, 2017), a state-of-the-art tool that extracts license terms from texts, and two natural language processing (NLP) techniques, i.e., regular matching (Andow et al., 2019) and semantic similarity (Le and Mikolov, 2014). Moreover, to study the influence of unlabelled training samples, we also conduct an ablation study, where LiDetector trained without unlabeled training samples is denoted by LiDetector^-. To conduct a fair comparison, we carefully implement the following NLP techniques and adapt them for license term identification. Specifically,

• •

  Regular Matching (Andow et al., 2019), which predefines a set of keyword patterns to guide license term identification. To implement this strategy, we manually analyzed license texts to find as more expressions of license terms as possible. Finally, 72 patterns were found for 23 license terms, as listed on our website (Xu et al., 2021a). We then use CoreNLP (Group, 2020) to split licenses into sentences and search for predefined expressions of license terms by regular matching.

• •

  Semantic Similarity (Karvelis et al., 2018), which utilizes doc2vec (Le and Mikolov, 2014) to represent text as a vector and searchs for similar expressions of license terms. To adapt this method, we trained the doc2vec model on the aforementioned 754 unlabeled licenses (i.e., 38,404 sentences), so as to learn the representations of license sentences. After that, we manually analyzed license sentences and collected a set of representative sentences for each license term. In total, we collected 51 representative sentences for 23 license terms, as listed on our website (Xu et al., 2021a). Finally, given a license sentence, we use the trained doc2vec model to predict its representation. Sentences with similar representations are considered to convey similar regulations about software use.

We conduct the comparative studies on the ground-truth dataset described in Section 4.1 (i.e., 400 labelled licenses with 21,844 labeled sentences). We randomly split these samples into the training and testing datasets by 4:1, and further split the training dataset for training and validation by 4:1. All the techniques and tools are evaluated on the same testing dataset.

Fig. 8 reports the results of each method. It can be seen that LiDetector outperforms the other methods, achieving 83.58% F1-score, followed by LiDetector^- (80.04%) and semantic similarity (75.85%). Among five methods, regular matching has the worst performance with 52.83% F1 score. The reason could be that predefined patterns limit the flexibility of expressions, leading to a low recall. Compared with recall, the precision of regular matching is relatively high due to the strict matching strategy. It can also be seen that semantic similarity outperforms regular matching and FOSS-LTE. The results indicate that semantics of license sentences can be learned by the doc2vec model, so that sentences with similar representations contain similar license terms. Moreover, we can also observe that the precision of FOSS-LTE is the lowest among all five methods. A possible reason could be that as a topic model, FOSS-LTE may be affected by noisy data during unsupervised learning.

Compared with FOSS-LTE, regular matching, and semantic similarity, both LiDetector and LiDetector^- have higher precision, i.e., 93.28% and 88.06%, respectively. The reasons behind are two folds: (1) the proposed method filters out license sentences which are irrelevant to license terms by preprocessing and clustering; (2) we employ a semi-supervised learning method that trains a sequential model on labelled sequences, which may lead to higher precision compared with unsupervised learning methods such as topic model in FOSS-LTE. From the ablation study, it can be seen from Fig. 8 that LiDetector (semi-supervised learning with unlabelled samples) outperforms LiDetector^- (supervised learning without unlabelled samples) for both precision and recall. The results indicate that pseudo labelling of unlabelled samples are predictive, and it is worthy of incorporating these unlabelled samples for training.

However, there are also corner cases that LiDetector fails to identify license terms. For example, in the project Statsite (Statsite, 2021), the license sentence “You may add your own copyright statement to your modifications and may provide additional or different license terms and conditions for use ….” actually grant rights to Relicense (No.3 in Table 1). However, LiDetector failed to identify this term due to the rareness of such expressions in the training dataset.

After identifying license terms, LiDetector aims to infer the attitudes towards these terms from license texts. To conduct a comprehensive study, in addition to FOSS-LTE (Kapitsaki and Paschalides, 2017), we also compare LiDetector with two NLP techniques, i.e., regular matching (Solakidis et al., 2014) and SST-based sentiment analysis (Socher et al., 2013). Again, these NLP techniques were implemented and adapted to the context of licenses, so as to infer rights and obligations.

• •

  Regular matching (Solakidis et al., 2014), which predefines a set of keywords to infer the attitudes implied by license sentences. To conduct a fair comparison, we use the same set of keywords (as listed in Table 3) for the baseline and LiDetector. Specifically, the baseline searches for the keywords that represent attitudes in the order of CANNOT, MUST, and CAN, which denote the prohibition, obligation, and right of a software product, respectively.

• •

  SST-based sentiment analysis (Socher et al., 2013), which learns a classifier that predicts the positive or negative attitudes from the Stanford Sentiment Treebank (SST). Since licenses are written in natural language, we train a LSTM model based on the SST sentiment dataset, so as to predict the attitudes of authors behind licenses.

To investigate the effectiveness of LiDetector, we conduct a comparative study on the ground-truth dataset (i.e., 400 labelled licenses with 21,844 sentences), and randomly split the dataset into training, validation, and testing datasets as described in Section 4.2. All the methods are evaluated on the same testing dataset. Moreover, to conduct a fair comparison, we evaluate the effectiveness of these methods on the same set of license terms, which has been correctly identified in the previous phase. For this reason, here we only compare the accuracy of these methods, since there are no false negatives in the evaluation and the recall cannot be calculated.

Table LABEL:table-phase3-eval shows the results on right and obligation inference. It can be observed that LiDetector outperforms the other methods in attitude inference, achieving 91.09% accuracy. SST-based sentiment analysis achieves a comparable performance with FOSS-LTE and regular matching, with the accuracy around 82%. Note that we utilize a model that has been well trained over the SST sentiment dataset. However, the results reported in Table LABEL:table-phase3-eval indicate that although license texts are written in natural language, methods of sentiment analysis cannot be directly applied to infer the stated conditions of software use.

By analyzing the results of FOSS-LTE, we found that FOSS-LTE does not distinguish between license terms and their attitudes. Instead, it predefines a set of phrases that represent regulations (e.g., MustOfferSourceCode), and utilizes a topic model to extract regulations from license texts. Compared with FOSS-LTE, LiDetector learns and extracts information from license texts with finer granularity. Specifically, it learns to identify license terms from texts, based on which it infers the implied attitudes towards the identified terms. By this means, LiDetector is capable of inferring regulations with more flexibility compared with predefined regulations.

For regular matching and LiDetector, we define the same set of attitude keywords, as well as the same order to search for the attitude keywords. However, we observe that simple regular matching is less effective than LiDetector in predicting attitudes. The characteristics of license sentences may contribute to the gap between performances of regular matching and LiDetector. Specifically, license sentences are typically long and complicated, which may contain massive tokens that are irrelevant to the attitudes towards a target term. Regular matching equally compares each token in the sentence with predefined keywords, which may introduce noise. In contrast, LiDetector filters out irrelevant tokens by grammar parsing, narrows down the scope of searching for permissive and restrictive expressions, and only analyzes powerful tokens that may have an influence on the attitude toward a target entity.

To investigate the overall effectiveness of LiDetector in incompatibility detection, we also compare LiDetector with three state-of-the-art tools, i.e., the SPDX Violation Tools (SPDX-VT) (Kapitsaki et al., 2017; Kapitsaki and Charalambous, 2019), Ninka (German et al., 2010) equipped with tldrlegal (kevin, 2012), and Librariesio (librariesio, 2015), a license compatibility checking tool for SPDX licenses. Since the other three tools are all based on the licenses on SPDX due to their inability on custom licenses, to make a fair comparison, we conduct this experiment and show the result in two ways: (1) Only the official licenses listed in the Software Package Data Exchange (SPDX) (Foundation, 2018) are considered for incompatibility detection. (2) All the licenses extracted from the project are considered (including the custom ones) for incompatibility detection.

Specifically, we randomly selected 200 projects from the 1,846 GitHub projects described in Section 2.3, and constructed a ground-truth dataset manually verified and cross-validated by three authors and a lawyer. In total, we extracted 1,298 unique licenses (including 191 project licenses and 1,107 component licenses), with 1,041 official licenses and 257 custom ones. The ground-truth dataset of incompatible projects has been made available online (Xu et al., 2021a). For each project, we first extract licenses in three forms (i.e., declared, referenced, and inline), and then use the aforementioned tools to detect the incompatibility issues. Note that, since we focus on license incompatibility detection for software projects, the FP and FN metrics are computed at the project level. Moreover, we also calculated the number of conflicts and overlaps for the these tools. In this paper, a conflict denotes a specific incompatibility issue, which means two incompatible attitudes towards the same license term. For instance, cannot disclose source versus must disclose source. We use overlap to denote the number of incompatible projects/conflicts that can also be detected by LiDetector.

Table 8 shows the incompatibility detection results on SPDX licenses only and all the extracted licenses. As for the results on SPDX licenses only, it can be seen that LiDetector detects 14,586 conflicts in 157 projects, while SPDX-VT only finds license incompatibility in 71 out of 200 projects, all of which can be detected by LiDetector. Note that LiDetector filters all official licenses whose regulations have already been known. For this reason, when only considering the official licenses in SPDX (SPDX, 2021b), there are no false positives and false negatives. Since SPDX-VT only predefined a graph to denote the compliance relationships between a set of licenses, the output of SPDX-VT is relatively coarse-grained (i.e., without detailed explanation of how licenses conflict with each other). Therefore, the number of conflicts detected by SPDX-VT are not presented in Table 8. It can be seen that the number of false positives reported by SPDX-VT is 6. However, the FN rate of SPDX-VT is 58.33%, nearly 30 times higher than that of LiDetector for all extracted licenses. By analyzing the process of SPDX-VT, we found that it designs a strict rule that only a set of license texts are identified and analyzed to detect incompatibility. However, the graph defined by SPDX-VT only includes 20 popular licenses, other licenses can not be detected by SPDX-VT.

For the results on all extracted licenses, among 200 projects, LiDetector identified 22,941 conflicts in 169 projects, with 10.06% FP rate and 2.56% FN rate. Ninka equipped with tldrlegal identified 13,978 conflicts in 144 projects, with 15.97% FP rate and 22.44% FN rate. It can be concluded that LiDetector has the superiority over Ninka (equipped with tldrlegal) from the respects of both precision and recall. By analyzing the reported results of Ninka, we found that some licenses are customized by authors of software products, which cannot be identified by Ninka. For instance, the component license in Fig. 2a is a custom license that cannot be identified by Ninka. Therefore, Ninka equipped with tldrlegal cannot detect the incompatibility issue in Fig. 2a. In addition, some licenses are exceptions of common open source licenses (i.e., license variants generated by developers based on popular licenses, thus resulting in the modification of its term attitudes), which regulates different rights and obligations but misidentified by Ninka. Fig. 9 shows a custom license which is an exception of GNU 3.0. In this case, LiDetector first identified that the license referenced GNU 3.0; then, it fed the rest text into the probabilistic model and inferred “CAN Statistically Link” from the text. However, Ninka only identified the license as GNU 3.0 ignoring the custom exceptions. As a result, the accuracy of Ninka limits its effectiveness in detecting license incompatibility.

Librariesio (librariesio, 2015) identified 169 incompatible projects, with 23.67% FP rate and 17.31% FN rate. Similar to SPDX-VT, the number of conflicts detected by Librariesio are also not presented in Table 8, since Librariesio provides no detailed explanation about how licenses conflict with each other. By analyzing the results of Librariesio and LiDetector, we found that the FP rate of Librariesio is more than twice as high than that of LiDetector and the FN rate of Librariesio is almost 8 times higher. The reason are two folds. First, Librariesio detects incompatibility between a set of SPDX licenses, while other licenses are ignored. Second, Librariesio detects incompatibility with a predefined set of heuristic rules, which might not be suited for large amounts of licenses which are flexible in expressions.

It can also be seen that the FP rate of LiDetector is 10.06%. By analyzing the false positives, we found that some license terms were not correctly identified from license texts, especially for license terms such as Statically Link and Relicense. The reason behind is that these license terms do not as frequently occur as other terms in the training dataset, which poses challenges in identifying these terms. We note that false negatives in the first phrase (i.e., license term identification) could lead to both false positives and false negatives in incompatibility detection. Another reason for false positives is the limitation of Stanford CoreNLP (Group, 2020). For instance, in the project Blosc (Blosc, 2021), there is a license sentence: