Socialz: Multi-Feature Social Fuzz Testing

Search-Based Software Testing (SBST) is a technique that leverages optimization search algorithms to solve software testing problems (McMinn, 2011). This approach is widely used in both industrial and academic sectors, including at Facebook, where it is employed to test the behaviour of both the system and its users (Alshahwan et al., 2018).

In social networks, testing goes beyond simply assessing the behaviour of the system and involves evaluating the interactions between users facilitated by the platform. To that end, Web-Enabled Simulation (WES) simulates the behaviours of a community of users on a software platform using a set of bots (Ahlgren et al., 2020). Traditional tests, on the other hand, involve executing a predetermined series of input steps. WES is run in-vivo but in a shadow copy of the system, hence as a separate “digital twin”, which allows for testing without risk to real user data (Ahlgren et al., 2021). Both “digital twins” and WES have widespread industrial applications, not only in OSNs but also in robotics, manufacturing, healthcare, and transport (Jiang et al., 2021; Rasheed et al., 2020).

In addition to testing, there are also methods for formally verifying the correctness of social network software and systems. Formal verification of social network protocols and algorithms ensures security and reliability by ensuring access to content is subject to both user-specified and system-specified policies (Cheng et al., 2012; Kafalı et al., 2014). Model checking can be applied at various levels of abstraction, from high-level network properties to the implementation of individual components (Pardo and Schneider, 2017). This approach can be used in combination with other testing techniques, such as simulation or testing with software-controlled bots, to provide a more comprehensive evaluation of a social network’s behaviour and performance (Pedersen et al., 2021).

We adopt definitions from Manes et al. (2018), who define fuzzing as a software testing methodology that involves injecting unexpected or randomised input data into a program-under-test to uncover defects or bugs. A specific application of fuzzing, called fuzz testing, evaluates the security policy violations of the PUT. The tool used to perform fuzz testing is known as a fuzzer.

The inputs used in fuzzing can be selected either randomly, with each element having an equal chance of being chosen, or through guided methods such as syntactic or semantic models (Mariani et al., 2015). Evolutionary fuzz testing is a variant of fuzz testing that leverages evolutionary algorithms to optimise the input data. Research has shown that it is effective in discovering a wide range of vulnerabilities, including those that are difficult to detect with traditional testing methods. For example, Li et al. (2019) demonstrate V-Fuzz, a vulnerability-oriented evolutionary fuzzing framework that combines vulnerability prediction with evolutionary fuzzing to reach potentially vulnerable code. They test various open-source Linux applications and fuzzing benchmarks. For Android applications, Cotroneo et al. (2019) introduce a coverage-guided fuzzing platform that demonstrated to be more efficient than blind fuzzing. Similarly, Zhong et al. (2022) employ a constrained neural network evolutionary search method to optimise the testing process and efficiently search for traffic violations.

Although fuzzing is widely used, to the best of our knowledge, no research has been conducted to fuzz test a social network system.

When it comes to social fuzz testing, the actions a user takes need to be determined, such as “follow a particular person”. In such a case, defining a user that achieves exactly this goal is straightforward, as a developer can easily translate the desired outcome into a specific interaction. However, creating a user with a more complex behaviour, such as “a virtual user should be highly active but not very central to everything that is going on”, is not as simple. Mapping the desired interaction between the virtual user and its environment is challenging due to the intricate interplay, even though the activity and centrality calculations may not be black boxes by definition. This issue becomes even more complex when designing a group of virtual users within a social network that can interact with each other in various ways.

We propose a practical solution to addressing such issues by treating the user features as black box functions and utilising heuristic approaches like novelty search (Risi et al., 2009) or evolutionary diversity optimisation (Ulrich and Thiele, 2011); this has been made possible only recently by algorithmic advancements in diversity optimisation with multiple features.

To characterise users, we investigate three features that we consider to be non-trivial in the sense introduced in Section 2.3: given these features, a developer may struggle to manually design a set of virtual users that exhibit a spread of desired community interactions. Our chosen features allow us to characterise how active a user is, what is its relative importance and what kind of interactions the user is involved in: First, the graph degree of centrality measure of the nodes quantifies how active a user is in the network, i.e. how many events are submitted. This measure is often used as a notion of popularity in social networks (Singh, 2020), as nodes with a large number of relationships are considered more powerful and central, but has a limitation in that it only takes into account local knowledge of the network topology. Hence, we introduce an additional centrality metric to supplement its analysis next.

Second, to assess the relative importance of a user on the network, we utilise the PageRank algorithm (Page et al., 1999): it is fast to compute, well suited for a directed network such as ours and has been proven to be effective in characterising users (Kumar and Kumar, 2021).

Third, to characterise the types of actions a user performs — for example, a user may submit only PushEvents, or only ForkEvents and PullRequestsEvents — we represent each combination as a binary vector and then consider the corresponding decimal value as that user’s event type.⁴⁴4Because the number of users is much larger than the number of possible combinations, and because we aim for diversity, we conjecture that variations to this mapping procedure only have minor effects on the overall outcomes. We consider 15 combinations, as we have four event types that are not FollowEvents, and the combination of “user does not interact at all” is not allowed.

It is critical to emphasise that these three metrics are features, not objectives: no user is “better” or “worse” than another one, neither in a single-objective sense, nor in a multi-objective sense.

In our evolutionary setup, each individual is an interaction graph that represents how virtual users interact in a social network. In particular, each individual is an edge list that contains all the necessary information of our graph: the source node, the target node, and the type of event. To evaluate our graphs, we have defined the following six steps.

First, we transform the edge list into an two-dimensional adjacency matrix. This adjacency matrix has four areas that reflect the interactions repo-repo, repo-user, user-repo, and user-user.

Second, we record the interactions between users and repositories in the repo-user and user-repo areas by summing the number of events that occur between each repository and user. Each event has a weight of one, regardless of its type. At present, as we do not further differentiate, the repo-user and the user-repo areas are mirrored versions of each other.

Third, as there are no interactions between repositories in our approach, the repo-repo area is always filled with zeros.

Fourth, we use the user-user area to store FollowEvents. It is initially empty, and we fill it by evaluating the cosine similarity of the users based on their interactions with repositories (areas user-repo, repo-user). If the cosine similarity is greater than zero for a pair of two users, then we set the respective entry to 1. The diagonal is set to 0 as users cannot follow themselves. The resulting matrix for the Original dataset looks like this (users 658 and 659 are chosen to show non-zero data, as the matrix is sparsely populated):

Fifth, with the FollowEvents incorporated into our edge list, we calculate the PageRank score and degree of centrality of each node. For the event type feature, we filter our data to only include user nodes and map each user node to the combination of events they were involved in.

Finally, we calculate the star-discrepancy score for the interaction graph.

Our rationale for the decision to create FollowEvents between two users based on the simple criterion that the cosine similarity across all events (for these two users) is greater than zero is three-fold and mostly based on practical considerations: (1) we make the assumption that users who create similar events may be likely to follow each other, (2) the approach is deterministic and thus saves memory (at the cost of computation time), and (3) it reduces the search space by allowing us to generate community interactions.

We employ a diversity optimisation approach using the star-discrepancy measure, based on (Neumann et al., 2018). The star-discrepancy measures the regularity with which points are distributed in a hypercube, and in particular with respect to all axis-parallel boxes $\left[0,\ b\right]$, $b\ \in\left[0,\ 1\right]^{d}$ that are anchored in the origin. Hence, this metric helps us evaluate how evenly the points are distributed in the feature space. In our case, each point represents a user with its coordinates defined by the three above-described metrics. We linearly scale all three metrics into $\left[0,1\right]$.

We use a $\left(1+20\right)$-EA, and in each mutation, we randomly add and delete edges, where the particular action and the particular edge are chosen uniformly at random. When deleting edges, we do not allow nodes to be disconnected, in which case we resample.

To aid the convergence, we utilise a success-based multiplicative update scheme that can lead to faster solution convergence (Doerr and Wagner, 2018). This scheme provides a dynamic mutation rate for the EA based on the performance of the offspring. If an iteration is successful, meaning an offspring is not worse than the current solution, the mutation rate is increased by a constant factor $A=2$. If the offspring is not better, the mutation rate is decreased by a constant factor $b=0.5$. The initial per-edge mutation rate is $1/n$, where $n$ is the number of edges, which is the total number of events that are not FollowEvents.

In summary, our evolutionary approach to diversified community interaction works as follows. We pass an interaction graph as an edge list to our evolutionary algorithm, mutate the edges as described, compute the user’s similarity to add FollowEvents and then create our graph to compute PageRank and centrality for each user and map the users to the combination of events they were involved with. With these three features, we compute a graph’s star-discrepancy score and, by means of our evolutionary algorithm, iteratively keep improving.

We start by using the original edge list of 6,742 events to calculate the similarity between the 1,523 users, resulting in an edge list of 397,224 events with a star-discrepancy score of 0.305 in the three-dimensional feature space. Then, we use this as the initial definition of the community interaction on our server, and apply the previously described evolutionary approach. We perform 30 independent evolutions, each for 10,000 generations, with each run taking approximately 30 hours. This results in interaction graphs with star discrepancies between 0.01107 and 0.01166.

Figure 2 shows the evolution over time. The self-adaptive parameter control appears to work well: (1) the number of mutations increases very quickly to several hundreds resulting in a quick improvement in diversity, (2) the number of mutations then gradually decreases to tens of mutations from 6,000 generations on, while still resulting in further improvements of the diversity.

A natural question is how to compare the Original and Evolved edge lists, because they are of notably different sizes? Examplarily, we answer this using a practical approach. First, of the 30 independent runs from Stage 2/3, we select the interaction graph with the lowest star-discrepancy; its evolved edge list contains 433,054 events with a corresponding star-discrepancy score of 0.01107 for 1,523 users. Next, to compare the Original and Evolved edge lists, we craft additional datasets using two approaches. The first approach creates a larger version (called “Simple”) of the original edge list by copying only the existing events until the size of this simple version matched that of the evolved edge list. The second approach generates new connections at random until the edge list reached the same size as the evolved one; the resulting community interaction is called “Random”. In both approaches, we ensure that the number of FollowEvents is the same, as these events are considerably more numerous than other types of events. By reducing the potential impact of differences in size on the validity of the results, these approaches allow for the creation of comparable versions of the Original and Evolved interactions.

Table 2 shows a first comparison of the four interaction graphs: the Original one that is directly based on GitHub data, its Simple (but larger) version, the Random version, and the Evolved one.

Figure 3 presents visualisations of the four communities. First, the left-most column shows projections of the graphs into 2d: edges refer to interactions between users and repositories; dot size represents the degree centrality of a node with larger dots indicating a higher degree centrality; and the colour of each dot represents the PageRank score of the node, where the colour range from green, less important, to yellow, higher score. As we can see, the Original and the Simple ones are (subjectively) close in structure. The Random one appears fairly homogeneous, and the Evolved one is much more diverse in terms of the distribution of PageRank scores and degree centrality.

Figure 3 complements these observations by showing the three features used to calculate the star-discrepancy score for each dataset, i.e. the degree of centrality of each user, their PageRank score, and the combination of events they are involved with. In particular, the discrepancy scores are 0.325 for the Original interaction graph, 0.327 for Simple, 0.069 for Random and 0.011 for Evolved.

The visualisations show that users in the Original and Simple datasets tend to cluster together and occupy a smaller space, while users in the evolved edge list and the random version of the original edge list appear to be more evenly distributed throughout the space. Interestingly, even the random version achieves a fairly diverse set of interactions, although the event types appear much less covered by the random dataset when compared to the evolved dataset. While it may appear that Evolved’s diversity in the PageRank and degree centrality subspace is less-than-impressive, in its own subspace ranges, the diversity is very even; Evolved’s evolution dropped large degree centrality users, and later (as evolution is diversity focussed), the boundaries would no longer be actively pushed outwards, relative to what can happen during Simple’s and Random’s construction. Despite this limitation, this data suggests that our evolutionary algorithm effectively improves the distribution of users in the feature space.

To assess the impact that the different datasets have on the server, we consider the processing of the community interaction as an actual benchmark in itself: as the hundreds of thousands events are processed between the 1523 users on the server, we observe how the system behaves. In the following, we outline the workflow used when executing the event and we present our observations.

External validity concerns the extent to which the results of a study can be generalised or applied to settings other than those used in the study. Our work was conducted on a specific dataset from GitHub and a GitLab CE server. This specific environment and dataset might not be representative of all possible scenarios. However, our choice was based on practical considerations (for example, we are unaware of another, substantial social network for which interaction data is available as well as options to execute those interactions on a production-quality server) and the widespread usage of these platforms in the developer community. In addition, the differences among the Original, Evolved, Simple, and Random datasets might not capture the entire spectrum of possible community interactions. This limitation might affect the generalisability of our findings across other datasets.

Internal validity pertains to whether a study establishes a cause-and-effect relationship. The creation of the “Random” dataset by generating connections randomly could introduce uncontrollable factors that might not be representative of real-world interactions. While it serves as a basis of comparison, it is crucial to be cautious when interpreting results derived from this dataset. To overcome a limitation in the number of followed users, we modified GitLab’s source code. Although we conjecture that this alteration did not adversely affect our results, it is essential to acknowledge that this change could introduce unforeseen variables into the experiment.

Construct validity evaluates whether the measures used for the study accurately represent the concept they are intended to measure. The method of crafting the “Simple” dataset by merely copying events until it matches the size of the evolved list might not be the most robust way of ensuring simplicity.