WIXLIB

1) Model InferenceSTRINGr 1,374.125.230.240 192.168.1.89192.168.1.89 74.125.230.24074.125.230.240 192.168.1.89ResourceAbstractionr 1,1r 1,2r 1,3r 2,1r 2,2r 2,3INTr 1,4ResourceClusteringIr 1,2r 1,4r 2,2r 1,1r 2,1Fr 2,32) Behavioral Patternsr 1,1r 1,2r 1,4r 1,3r 1,3r 2,1r 2,2r 2,3Data flowPatternsr 1,3Ir 1,1r 2,1PChain 1r 1,2r 1,4r 2,2r 1,1r 2,1Ir 1,2r 1,4r 2,2FFIr 1,3TrWPrrRpSt1,21,4r 2,2r 1,1r 2,1Fr 2,3TrWPMWPPChain 23) Test Cases Generationr 1,1r 2,1TrWPrrWorkflowPatternsr 2,3r 2,3Ir 1,34) Test Cases ExecutionRpStTest Casesr 1,4r 1,1r 1,2r 1,3r 2,1r 2,2r 2,3r 1,1r 1,2r 1,3r 1,4r 1,1r 1,2r 1,3r 1,4r 1,1r 1,2r 1,3r 1,4Execution74.125.230.240 192.168.1.89192.168.1.89 74.125.230.24074.125.230.240 192.168.1.891,21,4r 2,2OracleFVerdict:Flaw foundin test1 and 2r 2,3TrWPMWPFig. 1: Architecture of our approach.store.com/ajax.php?action cart1) Resource AbstractionInput traces are sequences of pairs of HTTP requests andresponses. The first step of the inference phase consists ofcreating a synthesis of the resources. Our approach currentlysupports JSON data objects [17] and HTML pages. However,it can be easily extended to other types such as SOAPmessages [36].rootrootitemsitemsitem1We call abstract HTML page the collection of (i) its URL,(ii) the POST data, (iii) the anchors and forms contained inthe HTML code and their DOM paths, (iv) the URL in themeta refresh tag, and, if any, (v) the HTTP redirection locationheader. We call abstract JSON object a collection of (i) itsURL, (ii) the POST data, (iii) the pairs of value and path inthe object, and (iv) the HTML links if any HTML code iscontained. For example, Figure 2 shows the abstract resourceof the following JSON object:store.com/ajax.php?action word item2item1item2price 19.9price dec tax 1.6tax dec Fig. 2: Resource abstraction and syntactic type inference of aJSON data objectcase of ambiguity – e.g., id 20 can be both a number and astring, but being the first a subset of the second, it is consideredto be a number.{‘items’: {‘item1’: [‘price’:19.9,‘tax’:1.6],‘item2’: [ . ]}}2) Resource ClusteringFrom each abstract resource we extract a set of elementscorresponding to all possible parameters that appear in theURLs, in the POST data, and in all the links. Each elementis characterized by a name, a value, a path, and an inferredsyntactic type. Our approach supports the integer type, decimaltype, URL type, email address type, word type (alphabetical strings e.g., “add”, “remove”, . . . ), string type, list type(comma-separated values), and unknown type (i.e., everythingelse). The type is associated to each element by inspecting thevalues of the element. Obvious priority rules are applied inModern web applications map application logic operationsto different resources. For instance, the operation of displayingthe shopping cart could involve an initial HTML page containing the skeleton of the web page and then use a number ofasynchronous AJAX requests to populate the page with thelist of items, tax, available vouchers, and so on. We clusterthese resources in three phases. First, we relate asynchronousrequests to the resource that originated them, i.e., synchronousresource. Then we group together resources considering both3

(a)(b)login.php(c)r1do.php?action cartr2ajax.php?action cartr3do.php?action show(a)login.phpdo.php?action word ajax.php?action word (b)login.phpdo.php?action cartajax.php?action word do.php?action showFig. 4: (a) Clusters after comparing all the resources (b) Clusters after having identified parameters encoding a commandr4〈 r2〉If the similarity inside the same sub-groups is high (more than55%), and between different sub-groups is low (less than 45%),then we assume the parameter is used to specify an operationand we create a different node for each value. Otherwise weleave the cluster unmodified. The result of this phase is shownin Figure 4.b.Fig. 3: (a) Application-level actions, (b) URLs requested, and(c) abstract resources with list of originatorssimilarity and the originators. Third, we split a cluster if aparameter of its resources encodes a command rather thancarrying a value.The navigation graph is a directed graph G (C {I, F }, E) where C is the set of clusters, I the source node,F the final node, and E the set of edges. We place the edge(u, v) if there exists one input trace π in which a resourcer0 u immediately precedes a resource r00 v. Then, foreach rj at the beginning of each trace (i.e. π hrj , . . .i), weplace the edge (I, u) where rj u and for each rj at the endof each trace, (i.e. π h. . . , rj i) we place the edge (u, F )where rj u. Finally, we associate to each node u the set ofall the elements for every r u.During the first phase, we pre-process input traces toidentify AJAX requests. This can be done by checking the“X-Requested-With” HTTP request header [32] or by detectingJSON responses. After that, we associate each resource to itsoriginators. Figure 3 provides an example of this first phase.In Figure 3.c we have the HTML page r1 followed by thepage r2 . Then r2 requests r3 by using AJAX that enriches r2with new HTML code, or new client-side scripts. The examplethen ends with r4 that we assume to be caused by a link in r2or added by r3 . Figure 3.c also shows the list of originatorsof each resource. r1 , r2 , and r4 have no originators, while r3was originated by r2 .B. Behavioral PatternsIn the second phase, we cluster resources. In general, tworesources are grouped in the same cluster if they have the sameURL domain and path, the same GET/POST parameter names,and, if any, the same redirection URL. When comparingparameters we do not take into account their values, but onlytheir syntactic types. For example, the following three URLsare equivalent:Behavioral patterns are workflow and dataflow patterns thatare likely related to the logic of the application. We divideworkflow patterns into Trace Patterns, that model what usersnormally do in our input traces, and Model Patterns that modelwhat the navigation graph allows to be done. Finally, DataPropagation Patterns model how data is propagated throughoutthe navigation graph.store.com/do.php?action add&id 3store.com/do.php?action add&id 7store.com/do.php?action show&id 31) Trace PatternsWe compare first synchronous resources as explained before, and then the asynchronous ones. Two asynchronousresources are in the same cluster if they have the same URLdomain and path, GET/POST parameter names, redirectionURL, and the same originators.Trace patterns model the actions performed by the user inthe input traces. In particular, we focus on three patterns:Singleton NodesA node is a singleton if it is never visited more thanonce by any input trace. Some of the users may visitthese nodes, and some may not - but no one visits themtwice. For example, submitting a discount voucher canbe an operation observed in some of input traces butnone of them is submitting a voucher twice.During the last phase, we identify the parameters that areencoding a command rather than transporting a value. Foreach parameter we take the pages that have the same value asthat parameter. For example, the parameter action dividesthe gray cluster of Figure 4.a in two sub-groups, one for thecart value and one for the show value. We then computethe page similarity between pages in the same sub-group andbetween pages in different sub-groups. The comparison is doneby looking at the DOM path of HTML forms, their actionattribute (URL domain and parameter names), and the nameof the nested input elements. The function is applied to subgroups by calculating the percentage of pages that are similar.Multi-Step OperationsA Multi-Step Operation is a sequence of consecutivenodes always visited in the same order. This is verycommon in many functionalities in web applications.For example, payment procedures or user registrationsoften consist of a precise sequence of steps, and all4

TrWP MWPClust. ParametersaRpbStRpcStπ2Clust.Parametersx v 1 y v 2x v 1 y v 2axybz v 1 k v 1z v 6 k v 1bzkcw v 3z v 4 k v 5cwjmddParametersabTrWP MWPπ1dj v 7 m v 1Fig. 6: Propagation Chains: from traces to the navigation graphTrWP MWPRpefTrWPSt3) Data Propagation PatternsRpFig. 5: Example of behavioral patterns using π1ha, b, a, c, d, e, f, ei and π2 ha, c, d, e, f, eiA propagation chain is a set of parameters with the samevalue which is sent back and forth between the client and theweb application during the HTTP conversation. We say thattwo parameters have the same value if there are some inputtraces in which they hold the same value, and there are notraces in which the values are different (since the user does notperform the same actions in all the traces, a certain parametermay not be present in all of them). We say that the chain isclient generated if the initial value is chosen by the user, andserver generated otherwise. A similar classification is usedby Wang et al. [34]. However, their notion is limited to singleinput traces while ours is extended to traces of different lengthsand to the navigation graph. traces going through those processes always executethem in the same exact order.Trace WaypointsWe use the term waypoint to describe nodes that playan important role in the interaction between the userand the application. In particular, trace waypoints arethose nodes that appear in all the input traces. Forexample, if all our traces contain a purchase, then theredirection to the payment website (e.g., PayPal) is atrace waypoint.We compute propagation chains in two steps. First, weidentify the propagation chain of each value within a trace.Let us consider the example in Figure 6. Here, in the inputtrace π1 , the parameter x has the same value of z and ofk. In trace π2 , the parameter x is still equal to k, but it isnow different from z. Moreover, the same value matches theparameter m. Second, by comparing the chains of traces, weremove contradictions reaching the result shown in the rightside of Figure 6.2) Model PatternsModel patterns model the sequences of actions that areallowed according to the navigation graph:C. Test Case GenerationRepeatable OperationsNodes that are part of a loop in the navigation graphare associated to operations that can potentially berepeated multiple times.In this section we describe the generation of test cases. Thisis done by adopting a number of attack patterns that model howan attacker can use the application in an unconventional way.In particular, we focus on a set of actions an attacker couldperform: repeating operations, skipping operations, subvertingthe order of operations, and mixing parameter values acrossuser sessions. For each action we designed a pattern. Thesepatterns are presented in Figure 7 and are based on thenavigation graph of Figure 5. We enriched Figure 7 withnumbers for showing the order in which the nodes are visited.For simplicity, we are omitting the source node I and the finalnode F , respectively connected to a and e.Model WaypointsModel waypoints are nodes that belong to every pathin the navigation graph that goes from the source nodeto the final node. These nodes are not only visited inall input traces, but there is no way in the navigationgraph to bypass them. By definition, every modelwaypoint is also a trace waypoint but not vice versa.Figure 5 shows an example to better describe the differencebetween model and trace patterns. The example shows the behavioral patterns of a navigation graph extracted from two input traces π1 ha, b, a, c, d, e, f, ei and π2 ha, c, d, e, f, ei.The symbols St, TrWP, Rp, and MWP stand for, respectively,singleton nodes, trace waypoints, repeatable nodes, and modelwaypoints. The thick dotted line delimits the multi-step operation.It is important to note that, while the approach presentedin this paper is generic, the choice of the attack patterns needsto reflect a particular class of logic flaws (in our case, thesubversion of either the control or data-flow of the application).Other types of logic vulnerabilities, such as authenticationbypass, may require the use of other patterns (e.g., randomlyaccess administration pages) that could be added to our system5

Multiple Executionof Repeatable Singletons1a5Breaking Multi-StepOperationsa342ca123bBreaking Server-GeneratedPropagation Chainsb3c6625a1323bc4da567bc4da1Waypoints Detourbc4par x7e9d(a)7fe84dd10ef(b)7bb859826c''8dc'a111par1 xpar2 yd95fe6(d)(c)10ef11f(e)Fig. 7: Test case generation patternsbut that are outside the scope of our paper. However, the use ofcustom techniques to detect certain vulnerabilities is commonto many other tools and approaches - e.g., a technique designedto find SQL injections cannot be used out of the box to detectother types of input sanitization vulnerabilities.3) Breaking Server-Generated Propagation ChainsThe goal of this attack pattern is to tamper with the dataflow of the web application. An example of test case is shownin Figure 7.c. The first part of the test interacts with theapplication and captures the value x of a server-generatedpropagation chain. In the second part, we start another sessionand interrupt the propagation chain by replacing the value ofpar with x.1) Multiple Execution of Repeatable SingletonsSince web applications contain many server-generatedpropagation chains (e.g., all the item or message IDs), thisattack pattern may generate a very large number of test cases.Therefore, we focus only on two types of propagation chains:the ones containing unique values (i.e., that differ in all theinput traces and are therefore related to the session) and theones containing installation-specific values (i.e., values that areconstant only within the same installation).This pattern models an attacker that tries to execute anoperation several times. If the model has a node that isrepeatable and singleton, it means that even though there isa way to repeat an operation multiple times, this was neverobserved in our input traces. Therefore, the attacker tries tovisit it twice.Figure 7.a shows the steps of the test case. We select aninput trace that visits b (e.g., ha, b, a, c, d, e, f, ei), a repeatableand singleton node. Then we split it into two parts at the nodeafter the singleton (e.g., ha, bi and ha, c, d, e, f, ei). We callthese two parts prefix and suffix. Second, we find the shortestloop from the singleton node to itself (e.g., hb, a, bi). Finally,the test case is the concatenation of the prefix, the loop withoutthe first node, and the suffix.The test case generation is the following. First, we selectthe parameters belonging to the chain that appear inside anHTTP request. These parameters are called injection pointsand model the point in which an attacker can replace thevalue generated by the server. For example, in Figure 7.c theparameter par of the node d is an injection point. Second, weselect two traces from different user sessions that are visitingthe node of the injection point. The first is truncated at theinjection point and the second is appended to the first one.With reference to Figure 7.c, the two parts are respectively atthe left- and right-hand side.2) Breaking Multi-Step OperationsThis pattern models an attacker that breaks multi-stepoperations. For example, once the payment page is reached, theattacker goes back and adds an item into the cart. In general,there are several ways of breaking the multi-step operation ofFigure 5. The first approach is to use a different ordering (e.g.,ha, d, c, e, f i). A second approach is to interleave other steps.In this pattern, we focused on the latter approach in which werepeat a step already included in the multi-step later in the testcase. For example, in the test case ha, c, d, c, e, f i in Figure 7.bwe repeat c after d. In this pattern, we repeat c also after eand f , but not after a.4) Waypoints DetourWaypoints are operations that are executed always by allthe input traces such as payment, or providing shipping data.When these operations happen only once per input trace, theyseem to indicate some sort of milestone in the execution ofthe business process of the web application. In the waypointdetour pattern, the attacker tries to skip these type of operationsby using one of two possible techniques. If the waypoint nodeis not part of a propagation chain, we simply try to skip it.6

case execution and compare them with the logic property thatwe want to violate.Otherwise, we try to remove the part of the navigation graphbetween two waypoints, reconstructing the propagation chainsby fetching the missing data values from another user session.A simple way to express a logic property for shoppingcarts could be the following: if an order is approved for auser, then the user must have completed a payment for thecorresponding amount. In this formulation two events play acentral role: the fact that an order is placed, and the fact thata user has paid a certain amount. Another important aspect ofthis property is the time dependency between the two events.Since propositional logic can only express truth regardless ofthe time, in our approach, we model logic properties as LinearTemporal Logic (LTL) formulas [30, 23]. LTL adds temporalconnectives like O (once in the past) to traditional logicaloperators like (and), and (implies). This enables us toverify whether one event will eventually happen in the futureor it already happened in the past.Figure 7.d shows an example of this pattern. On the leftside we skip the waypoint d, while on the right side wecut the subgraph between a and d. In this second case, ifthe URL of node d depends on a value that appears in thesegment between a and d, we prepare another user session byselecting an input trace and interrupting it at d. The generationof this part is similar to breaking propagation chains. The firstuser session is then ha, b, a, c0 , c00 , di. Afterwards, we preparethe second user session that skips the sequence between aand d. In this example, there are two possibilities: skippinghb, a, c0 , c00 i or hc0 , c00 i. Figure 7.e shows only the latter. Inthis case the test case is the concatenation of ha, b, a, c0 , c00 , diand ha, b, a, d, e, f, ei. For this case we also support the variantin which the first user session is not interrupted at the noded.For example, the above logic property can be written inLTL as follows:ordplaced onStore(S) O(paid(U, I))D. Test Case Execution(1)where ordplaced , onStore(S), and paid(U, I) are respectivelythe events order placed, operation performed on the store S,and user U paid the price of item I. Now

an application looking for well-defined vulnerability patterns. However, traditional approaches focus mostly on the detection of input validation flaws, such as SQL injection and cross-site scripting. To date, more subtle vulnerabilities specific to the logic of a particular application are still discovered by manual inspection [33].