Hello everyone, I'm Yi Xiong Chen from Shanghai Jiaotong University. Today I'm going to present a novel type inference technique, which can enhance automated testing for RESTful web services. It is a joint work with Yang Yang, Zhan Yao Lei, Mingyuan Xia, and Zhengwei Zhi. The RESTful architecture is very popular nowadays.

Developers can easily build services supporting diversified client programs based on the RESTful architecture. Because this architecture is designed for exchanging data between applications implemented by different programming languages. However, this nature makes RESTful parameters weakly typed, because languages have different specifications and implementation of non-primitive data types.

And therefore only several common primitive data types can be used in the RESTful protocol. For example, if an Android application wants to send a Java data object X to a service implemented by Python, it has to first serialize X to a string, and then the service needs to deserialize the string to get a Python data object.

Other parameters like timestamps are represented by strings to avoid potential overflow problems. Real numbers like prices are also represented by strings to guarantee fixed decimal places. We can justify countless examples like this.

Our investigation on 27 popular RESTful services shows that about 67% of the API parameters are strings and 32% are numbers. So in the RESTful world, diversified data types collapse into very limited cases.

We even see some services using strings to represent almost everything. We call this phenomenon the type collapse problem. The type collapse problem is challenging for automated testing tools to generate effective test cases. Now imagine that this box search API in front of you is to be tested, and we give our testing tool a sample request.

We want the tool to generate test cases for the parameter publication date according to this sample request. If the tool only knows this parameter is a string, it will only generate very naive test cases, like a sentence of Shakespeare or a circle injection.

These test cases are mainly useless because they will be directly rejected by simple parameter checking. But if the tool could obtain this parameter actually requires dates, it will generate more expert and effective test cases, such as a 5-digit year date, an invalid February 29 of known years, and a negative timestamp date.

These test cases are more likely to pass parameter checking and trigger bugs. But unfortunately, due to the type collapse problem, this kind of information is usually hard to obtain, leading to ineffectiveness of existing automated testing tools.

So how can we obtain such fine-grained type information and make our automated testing tools smarter? Well, we observe that although data types collapse into primitive cases, value format features are always distinct and can be preserved across different programming languages.

Therefore, our solution is utilizing value formats to help model restful parameters. We propose FET, which stands for Format Encoded Type. A FET represents a parameter by both its data type and its value format.

And we propose FET lattice and FET inference algorithms to infer FETs for parameters to help automated testing tools to have a better understanding of parameters. We implement LIF, a trace-driven funding tool as a proof-of-concept of FET techniques.

Next, I will first briefly describe LIF and then elaborate how FET techniques work. Now we assume that a web service to be tested is already deployed in a production or pre-production environment, and some client applications communicate with it and exchange data via restful APIs.

LIF collects HTTP traffic between them and passes traffic to identify APIs and parameters. Then LIF applies FET inference on captured parameter values and gains fine-grained information of parameters. Finally, LIF generates requests according to the inference results and observes crashes or any other wrongful behaviors of the service.

We use LIF to test 27 popular commercial restful services, which are serving billions of end-users all over the world. LIF finds 11 distinct new bugs from these commercial services and witnesses 72% to

86% fuzzing time reduction when compared to state-of-the-art automated testing tools. LIF's good effectiveness and performance are leveraged by FET techniques, so now I'm going to introduce FET techniques in detail.

First of all, a FET is defined by a data type and a value format as mentioned. A value format is a set of values and we use regular expressions to define value formats. For example, for the hash FET, its data type is string and its value format is as presented.

Using regular expressions may not be the best choice in the theory, but still they have many advantages in this scenario. They are already familiar to developers, so they are easy to understand and extend. And although they are context-free, they can still distinguish different value formats, so they are the best choice in practice.

And different FETs are organized by a partial order. And intuitively speaking, upper FETs describe parameters in causal grains while lower FETs describe parameters in final grains.

For example, the hash FET represents any hex strings with more than 16 characters, while its child, MD5, represents hex strings with exactly 32 characters. We investigate API documents and the specifications of popular public RESTful services, such as Google Map, AWS, Twitter and GitHub.

And construct 21 FETs organized in five levels to represent all common parameters in the world. These FETs together with the partial order compose a FET lattice.

You can find more formal definition details in our paper and you can get access to this lattice model on Figshare. Now we will move on to FET inference. But before that, let's look at FET acceptance, which is an important basic concept for FET inference.

A FET is said to accept a value if and only if the data type of the value is convertible to the data type of the FET and the value matches the value format. For example, for a given MD5 string, it is accepted by the string FET because their data types are both strings and the value matches the format.

And this value is also accepted by hash and MD5 FETs because the value matches both formats. But it is rejected by shaven FET because the format is not matched.

And there are two special FETs in the lattice called top and bottom. Top accepts any types with any values, while bottom accepts nothing. And as we can imagine, a value usually can be accepted by multiple FETs. We call the greatest lower bound of them the minimum acceptance, which is MD5 in this case.

The minimum acceptance is meaningful for a parameter because it describes the value in the finest grain. Or in other words, the value matches the minimum acceptance best. Now with the concept of FET acceptance, we will discuss FET inference.

For a given parameter value, the main goal of FET inference is to find the minimum acceptance of the value, because as mentioned, the minimum acceptance provides critical information. FET inference searches from the top FET and the value is accepted by top because top accepts all values.

And then we try the children of top and only the string FET accepts the value because this value is string typed. We keep searching until no lower FETs accept the value and thus the minimum acceptance is found,

which is the ISO 8601 FET in this case. Notice that the predecessors of the minimum acceptance accept the value but describe it in a causal grain, while the siblings reject it but describe other similar values in the same grain.

These features are all useful for test case generation. Therefore, the inference result of a single value is a tree consisting of the minimum acceptance, the predecessors and the siblings. And of course, a parameter may take multiple possible values that are inferred through distinct FET trees in practice.

So the inference result of such a parameter is the merging of all FET trees of the values. For example, if FET inference witnesses two values of this parameter, one is an ISO data string and the other is an MD5 string, they will be respectively inferred through two different FET trees.

One takes the ISO 8601 FET as the minimum acceptance, while the other takes MD5. So the final inference result of this parameter is the merging of these two FET trees. Now I'm going to elaborate how to generate test cases based on FET inference results.

As mentioned due to the type collapse problem, for such a parameter, without FET techniques, the only thing a testing tool can know is that it's a string, therefore it has to try a very long list of candidate values, such

as empty strings, extremely long strings, meta characters, malformed URLs and invalid package names. However, most of them will be directly rejected by parameter checking, and therefore are not able to reach actual core logic and trigger any bugs.

But now with FET techniques, a testing tool can know it's an ISO data string, so it only needs to try a short but targeted list for each FET in the tree, and just ignore test cases corresponding to FETs that are not in the tree. More importantly, it can understand the meaning of the parameter and then dynamically mutate

the value rather than just pick up values from a predefined static candidate dictionary. For example, it can generate a test case by changing the time zoom from Central European Time to Pacific Time in this case.

So that's how FET techniques work. And to verify if the FET techniques actually solve the type collapse problem, we study our FET inference accuracy on 50 RESTful APIs of Twitter and GitHub.

We assume that API documents provided by the service developers are the ground truth, so we validated inference accuracy by comparing inference results with API documents. And we observe three levels of matching, exact matches, partial matches, and mismatches.

An exact match means the inference result has the exactly same data type and the value format as the ground truth. A partial match means the result is a superset of the ground truth, which is benign for it only makes a father to generate a small set of useless test cases.

And a mismatch means the value format is not yet supported by the current FET lattice. The figure on the left depicts the rations of these three levels of matching. As we can see, most of the results are good, but indeed, there are cases FET inference does not support.

There are many binary array parameters for file uploading, while there are only a very small part, and binary fuzzing is another very different research topic. So let's just focus on the exact matches. The figure on the right depicts the distribution of exact matches.

The inner ring is the distribution of parameter data types and the outer ring is the distribution of inference results. The distribution of data types is a little different from our investigation, but numbers and strings are still the main challenges.

And as we can see, they are breakdown by FET inference into much smaller slices in balance. This is exactly how FET techniques restore fine-grained type information for RESTful parameters. And as mentioned, we apply LEAF to 27 real-world commercial RESTful services and

compare it with existing fuzzing tools, such as Brube Suite, Fuzz API and TNT Fuzzer. The result is encouraging, and LEAF's auto-performance together with the accuracy of FET inference gives solid evidences that FET techniques help an automated testing tool to have a better understanding.

So in conclusion, we investigate the type collapse problem and propose FET techniques to solve the problem, and we implement LEAF and apply it to 27 real-world services.

Our result shows that LEAF has better bug-finding capability with significant performance improvement as compared to state-of-the-art tools. That's all. Thanks for listening.