TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time (Extended Version)

Machine learning (ML) has become a fundamental tool in malware research within the academic security community, with its applications spanning a wide range of domains. While the high performance figures associated with machine learning solutions might lead one to believe that the issue of malware classification is practically solved, this is far from true.

Malware classifiers are challenged by the dynamic nature of operational environments and attacking techniques. The constant emergence of new malware variants and families often leads to a degradation in the predictive accuracy of these classifiers over time. Ensuring temporal consistency is therefore a critical factor in evaluating the effectiveness of these classifiers.

We identify two types of experimental bias: spatial bias and temporal bias. Spatial bias occurs when there are unrealistic assumptions about the ratio of goodware to malware in the dataset, which must be consistently enforced during the testing phase to mimic a realistic scenario. Temporal bias occurs when there is a temporal inconsistency between the training and testing datasets, which can lead to the integration of future knowledge into the training phase or create unrealistic settings, especially for concept drift detection.

We believe that the pervasiveness of these issues is due to two main reasons: first, possible sources of evaluation bias are not common knowledge; second, accounting for time complicates the evaluation and does not allow a comparison to other approaches using headline evaluation metrics such as the F1-Score or AUROC.

Previous works by Sommer and Paxson, Rossow et al., and Kouwe et al. propose guidelines for sound security evaluations, but none of them identify temporal and spatial bias or quantify the impact of errors on classifier performance. While Allix et al. and Miller et al. identify initial temporal constraints in Android malware classification, we demonstrate that recent work following their guidelines still suffer from temporal and spatial bias. Our paper is the first to identify and address these sources of bias with novel, actionable constraints, metrics, and tool support.

In this study, we primarily focus on two popular malware detection approaches: DREBIN and DEEPDREBIN. To ensure a robust experimental framework, we have thoroughly re-implemented both DREBIN and DEEPDREBIN based on the detailed methodologies outlined in their foundational papers. In contrast, we have excluded MAMADROID from this study due to its limited efficacy, as observed in our previous analysis spanning 2014 to 2016.

It is therefore essential to determine whether malware is a minority, majority, or equal-sized class compared to goodware. For instance, industry telemetry by a key player suggests that around 6% of Android apps are malicious. On the other hand, AndRadar measurement study indicates that the ratio of Android malware in the wild is approximately 8%. The 2017 Google’s Android security report estimates the malware percentage to be between 6% and 10%, while in 2023 the AndroZoo dataset analysis reveals an incidence of 16.3% of malicious apps among the whole dataset.

To stabilize the percentage of malware in our dataset, we choose to set it to 10%, which is an approximate average across different estimates, with monthly values ranging from 8% to 12%. It is important to emphasize that the decision to set the malware percentage at 10% in our dataset should not be interpreted as a universal benchmark for Android malware detection.

Concept drift is a problem that occurs in machine learning when a model becomes obsolete as the distribution of incoming data at test-time differs from that of training data, i.e., when the assumption does not hold that data is independent and identically distributed (i.i.d.). In the ML community, this problem is also known as dataset shift. Time decay is the decrease in model performance over time caused by dataset shift.

Concept drift in malware combined with similarities among malware within the same family causes k-fold cross validation (CV) to be positively biased, artificially inflating the performance of malware classifiers. K-fold CV is likely to include in the training set at least one sample of each malware family in the dataset, whereas new families will be unknown at training time in a real-world deployment.

We identify a novel form of temporal bias that arises when goodware and malware correspond to different time periods, often due to originating from distinct data sources. This situation can lead to the classifier learning to distinguish between applications from different time periods rather than differentiating between goodware and malware, thereby resulting in artificially inaccurate performance. For instance, spurious features such as new API methods may exhibit strong discriminatory power simply because malicious applications predate the introduction of those APIs.

We identify two main types of spatial experimental bias based on assumptions on percentages of malware in testing and training sets.

Spatial experimental bias in testing. The percentage of malware in the testing distribution needs to be estimated and cannot be changed, if one wants results to be representative of in-the-wild deployment of the malware classifier. We change the percentage of malware in the testing set by randomly down-sampling goodware, so the number of malware remains fixed throughout the experiments. In this scenario, we can observe that TPs (i.e., malware objects correctly classified as malware) and FNs (i.e., malware objects incorrectly classified as goodware) do not change, because the number of malware does not increase; hence, Recall remains stable. The increase in number of FPs (i.e., goodware objects misclassified as malware) decreases as we reduce the number of goodware in the dataset; hence, Precision improves. Since the F1-Score is the harmonic mean of Precision and Recall, it goes up with Precision. This example shows how considering an unrealistic testing distribution with more malware than goodware in this context positively inflates Precision and hence the F1-Score of classifiers.

Spatial experimental bias in training. It is observed that as the percentage of malware in training increases, the hyperplane of the SVM shifts towards the goodware region. Specifically, it improves the Recall of malware while reducing its Precision. In order to minimize the overall error rate Err = (FP + FN)/(TP + TN + FP + FN) (i.e., maximize Accuracy), it is advisable to train the dataset with the same distribution that is expected in the testing. However, in certain cases, there may be a greater interest in identifying objects of the minority class (e.g., ”more malicious samples”) by improving Recall while ensuring a constraint on the maximum FPR.

We present a motivating example where we manipulate experimental biases to better illustrate the problem. The data presented in Table 1 reveal that both DREBIN and DEEPDREBIN exhibit significantly lower performance in realistic scenarios compared to settings similar to those described in prior works. This discrepancy can be attributed to unintentional experimental biases.

The last row of Table 1 shows that the realistic setting, where training is temporally precedent to testing, causes the worst classifier performance in the majority of cases.

To evaluate the classifier, the dataset D must be split into a training dataset Tr with a time window of size W, and a testing dataset Ts with a time window of size S. Here, we consider S > W in order to estimate long-term performance and robustness to decay of the classifier. We emphasize that, although we have the labels of objects in Ts ⊆ D, all the evaluations and tuning algorithms must assume that labels y_i of objects s_i ∈ Ts are unknown.

To evaluate performance over time, the test set Ts must be split into time-slots of size Δ. We now formalize three constraints that must be enforced when dividing D into Tr and Ts for a realistic setting that avoids spatio-temporal experimental bias. While C1 was proposed in past work, we are the first to propose C2 and C3—which we show to be fundamental.

If C3 is violated by overestimating the percentage of malware, the results are positively inflated. We highlight that, although the testing distribution δ cannot be changed (in order to get realistic results), the percentage of malware in the training φ may be tuned.

We introduce a time-aware performance metric that allows for the comparison of different classifiers while considering time decay. Point estimates are always to be preferred to represent the real performance of an algorithm. The cumulative estimates can be used to highlight a smoothed trend and to show overall performance up to a certain point, but can be misleading if reported on their own if objects are too sparsely distributed in some test slots Δ.

To facilitate the comparison of different time decay plots, we define a new metric, Area Under Time (AUT), the area under the performance curve over time.

We propose a novel algorithm that allows for the adjustment of the training ratio φ when the dataset is imbalanced, in order to optimize a user-specified performance metric (F1-Score, Precision, or Recall) on the minority class, subject to a maximum tolerated error, while aiming to reduce time decay. Also, we assume that the user already has a training dataset Tr and wants to use as many objects from it as possible, while still achieving a good performance trade-off; for this purpose, we perform a progressive sub-sampling of the goodware class.

As a result, if we want to maximize F1-Score for the malware class, we need to limit both FPs and FNs. if P = Pr, we minimize FNs, so we constrain FNR. And if P = Rec, we constrain FPR.

We introduce TESSERACT, an open-source performance evaluation framework that rigorously applies constraints C1, C2, and C3, computes AUT, and possesses the capability to refine a classifier utilizing our proposed tuning algorithm. TESSERACT functions comparably to traditional Python ML libraries, yet it distinctively requires not only the features matrix X and labels y, but also an array of timestamps t, which sorts the dates corresponding to each data entry.

We make TESSERACT’s code and data available to the research community to promote the adoption of a sound and unbiased evaluation of classifiers. The TESSERACT project website with instructions to request access is at https://github.com/s2labres/tesseract-ml/, and all experiments related code can be found at https://github.com/s2labres/tesseract-journal-experiments/.

Here, we show how our methodology can reveal hidden performance of DREBIN and DEEPDREBIN, along with their robustness to time decay. Both approaches show a similar trend of performance in the testing data. The 10-fold CV results are 0.85 and 0.84, with an AUT(F1, 48m) of 0.50 and 0.49 for DREBIN and DEEPDREBIN, respectively.

Focusing on the malware side, we observe that both F1-Scores and Recall rates initially decrease, followed by a modest recovery after Month 28. Precision remains stable in the first 24 months for both methods, then experiences a notable decline after Month 24 and generally remains lower thereafter. There is no obvious performance decay, apart from Month 39, from goodware’s side.

When evaluating performance with the AUT metric, a new feature in TESSERACT framework is that users can define the observation time window (τ, by default, it equals the full length of the testing period) for more detailed performance change. When we set the time window as default, where τ = 48-month, DREBIN and DEEPDREBIN show similar performances of 0.50 and 0.49, respectively. Notably, when τ gets even smaller, DEEPDREBIN exhibits more consistent and robust performance in the second year (Month 13 to 24) and maintains this trend across all smaller time windows (e.g., τ = 3-month, 6-month, and 12-month).

In our initial analysis documented in the original paper, the deep learning method appeared to outshine the other two traditional ML approaches (Alg1(Drebin) and Alg2(MaMaDroid)) in terms of robustness after enforcing C1, C2 and C3. However, upon closer inspection and a more extended evaluation, this claim does not hold consistently. It is true that during the first two year of evaluation, the deep learning approach demonstrated a better and relatively stable performance. Nonetheless, when considering the broader scope of the analysis, it becomes evident that the overall performance of the deep learning method aligns closely with that of traditional machine learning techniques, if retraining is not possible.

We first aim to maximize P = F1-Score of malware class, subject to E_max = 10%. After running Algorithm 1 on DREBIN and DEEPDREBIN, we set φ*_F1 = 0.55 for DREBIN, and φ*_F1 = 0.20 for DEEPDREBIN. We remark that the choice of φ*_F1 uses only training information and no test information is used—the optimal value is chosen from a 4-month validation set extracted from the one year of training data; this is to simulate a realistic deployment setting in which we have no a priori information about testing.

When trained with φ*_F1, a decrease in Precision is noted due to an increase in False Positives (FPs), while an increase in Recall is observed as a result of a decrease in False Negatives (FNs). This trade-off leads to a slight improvement of AUT for both classifiers. For each specific performance metric P, the tailored performance AUT(P, 48m) with φ*_P generally surpasses the performance achieved using the original training ratio σ̂ for both DREBIN and DEEPDREBIN. The notable exception is when focusing on Precision; in this case, the tuning slightly underperforms compared to the original training ratio.

Furthermore, a three-year evaluation window was also employed to assess the tuning algorithm. Aligning with the full dataset protocol, the first year of data from this three-year period was used to ascertain the optimal φ*_F1, and subsequent tests were conducted over the following two years. The optimal φ*_F1 was found to be 0.35 on both years 2015 and 2016 for both DREBIN and DEEPDREBIN. Our investigation strongly recommends the adoption of a dynamic tuning and testing regimen.

We now discuss the impact of the spatial and temporal bias on ML-driven detection performance in other domains: Windows Portable Executables (PEs) and PDFs. Intuitively, we could expect a slower onset of concept drift—along with a more gradual decline in model performance—in these domains. The Android ecosystem predominantly features goodware. Conversely, the ratio of malware to goodware in Windows PE and PDF domains is not easily quantified due to a lack of comprehensive evidence.

Our case studies on both EMBER and HIDOST reveal significantly less concept drift compared to the Android dataset, likely due to the more stable and predictable nature of malware evolution in these environments. This stability is likely linked to the slower OS development cycle in Windows PE and the consistent format and usage in PDFs. Notably, we find that applying our algorithm 1 to tune the malware-to-goodware ratio during the training process enhances detection performance in testing within these domains.

While our work does not propose novel delay strategies, it leverages TESSERACT to facilitate the comparative analysis of several popular approaches aimed at mitigating time decay. To quantify performance-cost trade-offs of methods to delay time decay, we characterize the following three elements:

• Performance (P): the performance measured in terms of AUT to capture robustness against time decay;
• Labeling Cost (L_c): the number of testing objects (if any) that must be labeled—the labeling must occur periodically (e.g., every month), and is particularly costly in the malware domain as manual inspection requires many resources (infrastructure, time, expertise, etc)—for example, Miller et al. estimated that an average company could only manually label 80 objects per day;
• Quarantine Cost (Q_c): the number of objects (if any) rejected by the classifier—these must be manually verified, so there is a cost for leaving them in quarantine.

The initial setup with no updates provides a baseline for performance. The training ratios with φ*_F1, however, exhibit better results for both classifiers without incurring additional costs, underscoring the importance of precise initial training/tuning settings for sustained performance.

The more data we label, the better retrained performance we get. For example, employing Active Learning (AL) with a 25% relabeling rate results in a labeling cost of 50,355 samples over 48 months for both DREBIN and DEEPDREBIN.

A comparison between the two rejection rows clearly shows that the application of the optimal training ratio φ*_F1 allows the classifier to more effectively quarantine dubious decisions. For DREBIN, TRANSCENDENT leads to a significant decrease in rejected samples—two-thirds less—while still improving performance: AUT(F1, 24m) rises from 0.658 to 0.717, and AUT(F1, 48m) from 0.537 to 0.558 respectively. Notably, TRANSCENDENT even enables DEEPDREBIN to outperform the AUT(F1, 24m) of the Active Learning scenario with a 25% budget, while quarantining fewer samples.

This article extends our work published at USENIX Security Symposium 2019. In this journal version, we focus on deepening and expanding the most promising aspects observed in our initial study on a larger dataset.