Especificación y Análisis Automático de Dependencias Inter-Parámetro en APIs Web

1 Specification and Automated Analysis of Inter-Parameter Dependencies in Web APIs Alberto Martin-Lopez , Sergio Segura , Carlos Müller , and Antonio Ruiz-Cortés Abstract—Web services often impose inter-parameter dependencies that restrict the way in which two or more input parameters can be combined to form valid calls to the service. Unfortunately, current specification languages for web services like the OpenAPI Specification (OAS) provide no support for the formal description of such dependencies, which makes it hardly possible to automatically discover and interact with services without human intervention. In this article, we present an approach for the specification and automated analysis of inter-parameter dependencies in web APIs. We first present a domain-specific language, called Inter-parameter Dependency Language (IDL), for the specification of dependencies among input parameters in web services. Then, we propose a mapping to translate an IDL document into a constraint satisfaction problem (CSP), enabling the automated analysis of IDL specifications using standard CSP-based reasoning operations. Specifically, we present a catalogue of seven analysis operations on IDL documents allowing to compute, for example, whether a given request satisfies all the dependencies of the service. Finally, we present a tool suite including an editor, a parser, an OAS extension, a constraint programming-aided library, and a test suite supporting IDL specifications and their analyses. Together, these contributions pave the way for a new range of specification-driven applications in areas such as code generation and testing. Index Terms—Web API, REST, inter-parameter dependency, DSL, automated analysis. F 1 INTRODUCTION Web Application Programming Interfaces (APIs) allow systems to interact with each other over the network, typically using web services [21], [41]. Web APIs are rapidly proliferating as the cornerstone for software integration enabling new consumption models such as mobile, social, Internet of Things (IoT), or cloud applications. Many companies are also exposing their existing assets as private APIs, fostering reusability, integration, and innovation within the boundaries of their own companies [21], [22]. Popular API directories such as ProgrammableWeb [36] and RapidAPI [39] currently index over 23K and 10K web APIs, respectively, from multiple domains such as shopping, finances, social networks, or telephony. Modern web APIs typically adhere to the REpresentational State Transfer (REST) architectural style, being referred to as RESTful web APIs [10]. RESTful web APIs are decomposed into multiple web services, where each service implements one or more create, read, update, or delete (CRUD) operations over a resource (e.g., an invoice in the PayPal API), typically through HTTP interactions. RESTful APIs are commonly described using languages such as the OpenAPI Specification (OAS) [33], originally created as a part of the Swagger tool suite [44], or the RESTful API Modeling Language (RAML) [38]. These languages are designed to provide a structured description of a RESTful web API that allows both humans and computers to discover and •A. Martin-Lopez, S. Segura, and A. Ruiz-Cortés are with the Smart Computer systems Research and Engineering Lab (SCORE) and the Research Institute of Informatics Engineering (I3US), Universidad de Sevilla, Spain. E-mail: {alberto.martin, sergiosegura, aruiz}@us.es •C. Müller is with the Research Institute of Informatics Engineering (I3US), Universidad de Sevilla, Spain. E-mail: [email protected] understand the capabilities of a service without requiring access to the source code or additional documentation. Once an API is described in an OAS document, for example, the specification can be used to generate documentation, code (clients and servers), or even basic automated test cases [44]. In this article, we focus on RESTful web APIs and OAS as the arguable standards for web integration. In what follows, we will use the terms RESTful web API, web API, or simply API interchangeably. Web services often impose dependency constraints that restrict the way in which two or more input parameters can be combined to form valid calls to the service, we call these inter-parameter dependencies (or simply dependencies henceforth). For instance, it is common that the inclusion of a parameter requires or excludes—and therefore depends on—the use of some other parameter or group of parameters. As an example, the documentation of the Twilio API [47] states that, when sending an SMS, either the body parameter or the media_url parameter must be set, but not both at the same time. Similarly, the documentation of the QuickBooks payments API [37] explains that, when creating a credit card, at least one of the parameters region or postalCode must be provided, although both of them are declared as optional. Current specification languages for RESTful web APIs such as OAS and RAML provide little or no support at all for describing dependencies among input parameters. Instead, they just encourage to describe such dependencies as a part of the description of the parameters in natural language, which may result in ambiguous or incomplete descriptions. For example, the Swagger documentation states1 “OpenAPI 3.0 does not support parameter dependencies and 1. https://swagger.io/docs/specification/describing-parameters/ 2 mutually exclusive parameters. (...) What you can do is document the restrictions in the parameter description and define the logic in the 400 Bad Request response”. The lack of support for dependencies means a strong limitation for current specification languages, since without a formal description of such constraints is hardly possible to interact with the services without human intervention. For example, it would be extremely difficult to automatically generate test cases for the APIs of Twilio or QuickBooks without an explicit and machine-readable definition of the dependencies mentioned above. The interest of industry in having support for these types of dependencies is reflected in an open feature request in OAS entitled “Support interdependencies between query parameters”, created in January 2015 with the message shown below. At the time of writing this paper, the request has received over 340 votes, and it has received 58 comments from 36 participants [30]. “It would be great to be able to specify interdependencies between query parameters. In my app, some query parameters become “required” only when some other query parameter is present. And when conditionally required parameters are missing when the conditions are met, the API fails. Of course I can have the API reply back that some required parameter is missing, but it would be great to have that built into Swagger.” This feature request has fostered an interesting discussion where the participants have proposed different ways of extending OAS to support dependencies among input parameters. However, each approach aims to address a particular type of dependency and thus show a very limited scope. Addressing the problem of modelling and validating input constraints in web APIs should necessarily start by understanding how dependencies emerge in practice. Inspired by this idea, in a previous paper we conducted a thorough study on the presence of inter-parameter dependencies in industrial web APIs [25]. For that purpose, we reviewed more than 2.5K operations from 40 real-world RESTful APIs from different application domains. As expected, we found that input dependencies are the norm, rather than the exception, with 85% of the reviewed APIs having some kind of dependency among their input parameters. More importantly, as the main outcome of our study, we presented a catalogue of seven types of dependencies consistently found in RESTful web APIs. These findings, and specifically the catalogue of dependencies (described in Section 2), serve as the starting point for this work. In this article, we first present a domain-specific language for the specification of inter-parameter dependencies in web APIs called Inter-parameter Dependency Language (IDL). Second, we present an approach for the automated analysis of IDL specifications using constraint programming. In particular, we present a general-purpose mapping showing how to translate an IDL specification into a constraint satisfaction problem (CSP). Then, we present a catalogue of seven analysis operations of IDL specifications and show how they can be automated using standard constraint programming reasoning operations. For example, given an IDL specification one may be interested to know if it includes any inconsistencies like parameters that cannot be selected (dead parameters), i.e., any request including them would violate some dependency, or whether a given call to the API satisfies all the dependencies. Our approach is supported by several tools including an (Eclipse) editor, a parser, an OAS extension (called IDL4OAS), a constraintprogramming aided library supporting the automated analysis of IDL specifications, and a complete test suite. To illustrate the potential of the approach, we assess the impact of our contributions in the domain of automated testing of RESTful web APIs. Specifically, we compared the effectiveness of random testing and IDLReasoner in generating valid requests (i.e., those satisfying all interparameter dependencies) and detecting failures in three commercial APIs. As expected, random testing struggled to generate valid requests: about 99% of the random requests generated violated inter-parameter dependencies in the APIs of Stripe and YouTube. In contrast, IDLReasoner generated 100% valid requests for all the services under test. More importantly, test cases generated with IDLReasoner revealed 17 times more failures than random testing (1,209 vs. 67). Beyond testing, our contributions prepare the ground for a new range of specification-driven applications in web APIs. For example, an API gateway supporting the automated analysis of IDL could automatically reject requests violating any dependencies, without even redirecting the call to the corresponding service, saving time and user quota. Code generators could automatically include built-in assertions to deal with invalid input combinations, preventing input-validation failures caused by violated dependencies. Analogously, interactive API documentations could be enriched with analysis capabilities to detect invalid calls even before invoking the API. The range of new applications is promising. This paper is structured as follows: Section 2 presents the catalogue of dependency patterns found in our systematic review of real-world APIs. Section 3 introduces the syntax of IDL using examples. Section 4 describes our approach for the automated analysis of IDL specifications. Our tool suite is presented in Section 5. Section 6 describes the evaluation of our approach. Section 7 describes the possible threats to validity and how these were mitigated. The related work is discussed in Section 8. Finally, Section 9 concludes the paper and presents future lines of research. 2 CATALOGUE OF DEPENDENCIES The contributions presented in this paper are built on the findings of a previous study by the authors on the presence of inter-parameter dependencies in industrial RESTful web APIs [25]. For the sake of understandability and to make our paper self-contained, we next summarise those results more relevant for this article, and redirect the interested reader to the original paper for further details. In our previous study, we reviewed more than 2.5K operations from 40 real-world RESTful APIs including popular APIs such as those of YouTube, Google Maps, Amazon S3, and PayPal. The results of the study showed that dependencies are extremely common and pervasive—they appear in 85% of the APIs under study (34 out of 40) across all application domains and types of operations. Specifically, we identified 633 dependencies among input parameters 3 (a) Dependency types. (b) Occurrences in APIs Figure 1: Distribution of dependencies by type and percentage of APIs. in 9.7% of the API operations analysed (248 out of 2,557). The collected data helped us characterise dependencies identifying their most common shape—dependencies in read operations involving two query parameters—, but also exceptional cases such as dependencies involving up to 10 parameters and dependencies among different types of parameters, e.g., header and body parameters. More importantly, we classified the inter-parameter dependencies identified into seven general types, described below. Before going in depth into each type of dependency, a number of considerations must be taken into account. First, for the sake of simplicity, dependencies are described using single parameters. However, all dependencies can be generalised to consider groups of parameters using conjunctive and disjunctive connectors. Second, dependencies can affect not only the presence or absence of parameters, but also the values that they can take. In what follows, when making reference to a parameter being present or being absent, it could also mean a parameter taking a certain value. Finally, when introducing each dependency type, we will make reference to Figure 1, which shows the distribution of dependencies by type (Figure 1a) and the percentage of subject APIs including occurrences of each dependency type (Figure 1b). Next, we describe the seven types of dependencies found in our study, including examples. Requires. The presence of a parameter p1in an API call requires the presence of another parameter p2. As previously mentioned, p1and p2can be generalised to groups of parameters and parameter-value relations. Based on our results, this is the most common type of dependency in web APIs, representing 35% of all the dependencies identified in our study (Figure 1a), and being present in 47.5% of the subject APIs (Figure 1b). As an example, in the GitHub API [17], when creating a card in a project, if the parameter content_id is present, then content_type becomes required. Or. Given a set of parameters p1, p2, . . . , pn, one or more of them must be included in the API call. As illustrated in Figure 1, this type of dependency represents only 3% of the dependencies identified in the subject APIs. Interestingly, however, we found that more than one fourth of the APIs (27.5%) included some occurrence of this dependency type, which suggests that its use is fairly common in practice. As an example, in the Google Maps Places API [18], when searching for places, both query and type parameters are optional, but at least one of them must be used. OnlyOne. Given a set of parameters p1, p2, . . . , pn, one, and only one of them must be included in the API call. As observed in Figure 1, this group of dependencies represent 17% of all the dependencies identified, and they appear in almost half of the APIs under study (47.5%). Among others, we found that this type of dependency is very common in APIs from the category media, where a resource can be identified in multiple ways, e.g., a song can be identified by its name or by its ID, and only one value must be typically provided. For example, in the Last.fm API [23], when getting the information about an artist, this can be identified with two possible parameters, artist or mbid, and only one must be used. AllOrNone. Given a set of parameters p1, p2, . . . , pn, either all of them are provided or none of them. Very similarly to the Or dependency type, only 6% of the dependencies found belong to this category, nonetheless, they are present in about one third of the APIs under study (30%). In the Yelp API [53], for example, when searching for businesses, the location can optionally be specified with two parameters, latitude and longitude, which must be used together. ZeroOrOne. Given a set of parameters p1, p2, . . . , pn, zero or one can be present in the API call. Figure 1 reveals that this dependency type is common both in terms of the number of occurrences (18% of the total) and the number of APIs including it (47.5%). As an example, in the search operation of the YouTube API [55], it is possible to filter results 4 Figure 2: ZeroOrOne dependency in the YouTube API. with four optional but mutually exclusive parameters, as depicted in Figure 2. Arithmetic/Relational. Given a set of parameters p1, p2, . . . , pn, they are related by means of arithmetic and/or relational constraints, e.g., p1+p2<100. As shown in Figure 1, this type of dependency is the most recurrent across the subject APIs, being present in half of them. Moreover, 17% of the dependencies found are of this type. An example of a relational dependency is found in the Twitter API [54]: when searching for tweets, the max_id parameter must be greater than or equal to the since_id parameter, otherwise no tweets will be returned. In the payments API Forte [11], the following arithmetic dependency exists: when creating a merchant application, this can be owned by up to four businesses, in which case the sum of the percentages cannot be greater than 100. Complex. These dependencies involve two or more of the types of constraints previously presented. Based on our results, they are typically formed by a combination of Requires and OnlyOne dependencies. As illustrated in Figure 1, we found 4% of complex dependencies, being present in 7.5% of the subject APIs. Figure 3 depicts a Complex dependency present in the Foursquare API [12]: if radius is used, then either intent is set to ‘browse’ or intent is set to ‘checkin’ and categoryId or query are present too. 3 INTER-PARAMETER DEPENDENCY LANGUAGE In this section, we present Inter-parameter Dependency Language (IDL), a textual domain-specific language for the specification of dependencies among input parameters in web APIs. Specifically, IDL is designed to express the seven types of inter-parameter dependencies identified in our study on real-world APIs and described in the previous section. This includes support for the dependencies discussed in the related OAS feature request in GitHub [30]. For the design of the language, we took inspiration from the input format of the combinatorial testing tool Pairwise Independent Combinatorial Testing (PICT) [35], by Microsoft, where constraints among input parameters can be defined using Figure 3: Complex dependency present in the GET /venues/search operation of the Foursquare API. invariants, conditional definitions (if/then/else), logical operators and relational operators. It is worth mentioning that IDL focuses on the definition of dependencies among parameters, but not in the definition of the parameters themselves. This is because IDL is specifically designed to be easily integrated into API specification languages such as OAS or RAML, where parameters are specified in different ways. Thus, in what follows, we simply assume that each parameter has a name and a domain. A simplified version of the grammar of the language is provided in Listing 1—the full version is available as a part of the implementation of IDL [19] and on the supplemental material provided with this article [43]. The key elements of the language are terms and predicates. Both of them can evaluate to true or false. A term is an atomic element of the language and can be represented by: (1) a parameter’s name (e.g., p1) being evaluated as true if the parameter is set (regardless of the value), or false otherwise; or (2) a parameter-value relation, evaluated as true if the parameter is selected and satisfies the relation. This relation can be defined using standard relational operators (e.g., p1>=100) or a wild card match—using the operator LIKE— if the parameter is a string (PATTERN_STRING in Listing 1), with ’*’ meaning zero or more characters and ’?’ meaning one character (e.g., p3 LIKE ‘test_*’). A predicate is a combination of one or more terms and dependencies joined by the logical operators NOT, AND, and OR. Parentheses are allowed in order to specify the operator priority. In what follows, we describe the IDL notation of each type of dependency. Requires. This type of dependency is expressed as “IF predicate THEN predicate;”, where the first predicate is the condition and the second is the consequence. The following listing shows two examples. Dependency in line 2, for instance, indicates that invocations including the parameters p1 and p2 should not include p3 nor p4, otherwise the call would be invalid. 1IF p1 THEN p2=='A'; 2IF p1 AND p2 THEN NOT (p3 OR p4); Or. This type of dependency is expressed using the keyword “Or” followed by a list of two or more predicates placed inside parentheses: “Or(predicate, predicate [, ...]);”. The dependency is satisfied if at least one of the predicates evaluates to true. Two examples follow. Dependency in line 1, for instance, specifies that valid invocations should include at least one of the parameters p1,p2 or p3. 1Or(p1, p2, p3); 5 1Model: 2Dependency*; 3Dependency: 4RelationalDependency | ArithmeticDependency | 5ConditionalDependency | PredefinedDependency; 6RelationalDependency: 7Param RelationalOperator Param; 8ArithmeticDependency: 9Operation RelationalOperator DOUBLE; 10 Operation: 11 Param OperationContinuation | 12 '(' Operation ')' OperationContinuation?; 13 OperationContinuation: 14 ArithmeticOperator (Param | Operation); 15 ConditionalDependency: 16 'IF' Predicate 'THEN' Predicate; 17 Predicate: 18 Clause ClauseContinuation?; 19 Clause: 20 (Term | RelationalDependency | ArithmeticDependency 21 | PredefinedDependency) | 'NOT'?'(' Predicate ')'; 22 Term: 23 'NOT'? (Param | ParamValueRelation); 24 Param: 25 ID|'[' ID ']'; 26 ParamValueRelation: 27 Param '==' STRING('|'STRING)*| 28 Param 'LIKE' PATTERN_STRING | Param '==' BOOLEAN | 29 Param RelationalOperator DOUBLE; 30 ClauseContinuation: 31 ('AND' |'OR') Predicate; 32 PredefinedDependency: 33 'NOT'? ('Or' |'OnlyOne' |'AllOrNone' | 34 'ZeroOrOne')'(' Clause (',' Clause)+ ')'; 35 RelationalOperator: 36 '<' |'>' |'<=' |'>=' |'==' |'!='; 37 ArithmeticOperator: 38 '+' |'-' |'*'|'/'; Listing 1: Simplified grammar of IDL. STRING,DOUBLE and BOOLEAN are standard data types. 2Or(p1, p3 AND p5, p6=='B'); OnlyOne. These dependencies are specified using the keyword “OnlyOne” followed by a list of two or more predicates placed inside parentheses: “OnlyOne(predicate, predicate [, ...]);”. The dependency is satisfied if one, and only one of the predicates evaluates to true. Examples of this dependency are shown below. The dependency in line 1, for example, indicates that valid invocations should include either the parameter p1 or the parameter p2 with value ‘B’, but not both at the same time. 1OnlyOne(p1, p2=='B'); 2OnlyOne(p1 OR p2, p3 AND (p4 OR p5)); AllOrNone. This type of dependency is specified using the keyword “AllOrNone” followed by a list of two or more predicates placed inside parentheses: “AllOrNone(predicate, predicate [, ...]);”. The dependency is satisfied if either all the predicates evaluate to true, or all of them evaluate to false. The dependency in line 1 below, for instance, indicates that valid calls are those including either the parameter p1 and p2 with value true, or conversely, those not including the parameter p1 and not including p2 with value true. 1AllOrNone(p1, p2==true); 2AllOrNone(p1 AND p2, p3 LIKE 'test_*'OR p4<10); ZeroOrOne. These dependencies are specified using the keyword “ZeroOrOne” followed by a list of two or more predicates placed inside parentheses: “ZeroOrOne(predicate, predicate [, ...]);”. The dependency is satisfied if none or at most one of the predicates evaluates to true. Two examples follow. Line 2, for instance, specifies that valid invocations must meet zero or one (but not both) of the two conditions between parentheses: (1) including the parameter p1, or (2) including the parameter p2 with a value less than or equal to 100. 1ZeroOrOne(p1, p2, p3, p4); 2ZeroOrOne(p1, p2<=100); Arithmetic/Relational. Relational dependencies are specified as pairs of parameters joined by any of the following relational operators: ==, !=, <=, <, >= or > (see examples in lines 1 and 2 below). Arithmetic dependencies relate two or more parameters using the operators +, - , *, / followed by a final comparison using a relational operator. Lines 3 and 4 of the following listing show examples of arithmetic dependencies. 1p1 < p2; 2p1 != p2; 3p1 + p2 - p3 *p4 == 100; 4p1 *p2 / ((p3 - p4) *p5) < 176.89; Complex. These dependencies are specified as a combination of the previous ones since, as previously mentioned, predicates can contain other dependencies. As an exception to this rule, predicates cannot include Requires dependencies to avoid over-complicated specifications (such dependencies can be expressed in simpler ways). The following listing shows some examples of complex dependencies. Dependency in line 1 combines four different types of dependencies: Requires,ZeroOrOne,OnlyOne and Relational. 1IF p1 THEN ZeroOrOne(p2, OnlyOne(p3, p4>p5)); 2AllOrNone(p1+p2<100, Or(p3=='A',Or(p4, p5>p6))); It is worth making a few general clarifications about the language regarding dependencies Or,OnlyOne,AllOrNone and ZeroOrOne. These are not strictly necessary, as they could be translated to several Requires dependencies. However, they are provided as syntactic sugar to make specifications succinct and self-explanatory. An example is given in the following IDL excerpt (lines 1-3). Secondly, they cannot contain negated elements within their parentheses, since such constraints can be expressed in simpler ways (lines 5- 6). Finally, they can optionally be preceded by the keyword “NOT” to negate the meaning of the constraint (see line 8 below for an example). 1AllOrNone(p1, p2); // Equivalent to 1) and 2): 2IF p1 THEN p2; // 1) 3IF p2 THEN p1; // 2) 4 5Or(p1, NOT p2); // Invalid dependency 6IF p2 THEN p1; // Equivalent to line 5 7 8NOT OnlyOne(p1, p2); // Valid negated dependency Listing 2 depicts the IDL specification of the Google Maps Places API [18]. It comprises seven operations, four of which have dependencies. The API has eight dependencies in total, including six out of the seven types of dependencies supported in IDL (all of them except the complex ones), namely: 6 •Line 2: If the parameter radius is used, then rankby cannot be set to ‘distance’, and vice versa. •Line 3: If the parameter rankby is set to ‘distance’, then at least one of the following parameters must be present: keyword,name or type. •Line 4: The parameter maxprice must be greater than or equal to minprice. •Line 7: Either both location and radius are used, or none of them. •Line 8: query and type are both optional parameters, but at least one of them must be used. •Line 9: Equal to line 4. •Line 12: One, and only one of the parameters maxheight and maxwidth must be used. •Line 15: If the parameter strictbounds is used, then both location and radius must be used too. 1// Operation: Search for places within specified area: 2ZeroOrOne(radius, rankby=='distance'); 3IF rankby=='distance' THEN keyword OR name OR type; 4maxprice >= minprice; 5 6// Operation: Query information about places: 7AllOrNone(location, radius); 8Or(query, type); 9maxprice >= minprice; 10 11 // Operation: Get photo of place: 12 OnlyOne(maxheight, maxwidth); 13 14 // Operation: Automcomplete place name: 15 IF strictbounds THEN location AND radius; Listing 2: IDL specification of Google Maps Places API. 4 AUTOMATED ANALYSIS The analysis of IDL deals with the extraction of information from IDL specifications. For example, given an IDL specification, we might be interested to know whether it contains errors (e.g., inconsistent dependencies) or whether a given API call is valid, i.e., it meets all the constraints defined in the specification. Performing these analyses manually is hardly possible in practice. In what follows, we present our approach for the automated analysis of IDL specifications using constraint programming. In particular, we first present the formal semantics of IDL by explaining how IDL specifications can be mapped to a constraint satisfaction problem (CSP). Then, we present a catalogue of seven analysis operations of IDL specifications and show how they can be automated using standard constraint programming reasoning operations. 4.1 Formal Semantics of IDL The primary objective of formalising IDL is to establish a sound basis for the automated support. Following the formalisation principles defined by Hofstede et al. [45], we follow a transformational style by translating IDL specifications to a target domain suitable for the automated analysis (Primary Goal Principle). Specifically, we propose translating IDL specifications to a CSP that can be then analysed using state-of- the-art constraint programming tools. A similar approach was followed by the authors to automate the analysis of feature models [3] and service level agreements [27], [28]. A CSP is defined as a 3-tuple (V, D, C)composed of a set of variables V, their domains Dand a number of constraints C. A solution for a CSP is an assignment of values to the variables in Vfrom their domains in Dso that all the constraints in Care satisfied. Table 1 describes the mapping from IDL to CSP. The first row of the table depicts how each input parameter is mapped to CSP variables, domains and constraints. Recall that both the name and domain of each parameter should be taken from the API specification (c.f. piand domain() function). For each parameter, two CSP variables are created: (1) one representing the parameter itself (c.f. pi), and (2) a Boolean variable to express whether the parameter is set or not (c.f. piSet). Optionally, we may also get information from the specification about whether each parameter is required (mandatory) or not. If a parameter piis required (i.e., it must be present in all API calls), the constraint piSet == true is added to the set of constraints C. The second and third rows of the mapping in Table 1 express how the terms are mapped to a CSP. Every time a parameter is found in a predicate, it must be checked whether the parameter is present in the API request. If so, it will evaluate to true, otherwise it will evaluate to false (c.f. piSet == true from the second row of the table). In the case of parameters having a relational condition with a value, it must also be checked that the parameter satisfies such condition (c.f. third row of the table). Finally, predicates and dependencies are defined recursively using the function map(E), where Eis either a term, a predicate or a dependency. Exceptionally, relational and arithmetic dependencies are only evaluated if all the involved parameters are present in the API request (c.f. last two rows in Table 1). As an example, Listing 3 shows the resulting CSP obtained as a result of applying the proposed mapping to the IDL specification of the Search operation in the Google Maps Places API, specified in Listing 2 (lines 1-4). Analogously, Listings 4 and 5 depict the CSP constraints derived from the Query and Get operations in Listing 2, respectively (lines 6-9 and 11-12). 1V={radius, radiusSet, rankby, rankbySet, keyword, 2keywordSet, name, nameSet, type, typeSet, 3maxprice, maxpriceSet, minprice, minpriceSet } 4 5D={int, Boolean, string, Boolean, string, Boolean, 6string, Boolean, string, Boolean, int, Boolean, 7int, Boolean } 8 9C={//ZeroOrOne(radius, rankby=='distance'); 10 ((radiusSet==true =⇒ ¬(rankbySet==true AND 11 rankby=='distance') AND ((rankbySet==true AND 12 rankby=='distance')=⇒ ¬radiusSet==true)) OR 13 ((¬radiusSet==true) AND ¬(rankbySet==true 14 AND rankby=='distance'))) AND 15 //IF rankby=='distance' THEN keyword OR name OR 16 // type; 17 ((rankbySet==true AND rankby=='distance')=⇒ 18 ((keywordSet==true) OR (nameSet==true) OR 19 (typeSet==true))) AND 20 //maxprice >= minprice; 21 (((maxpriceSet==true) AND (minpriceSet==true)) =⇒ 22 (maxprice ≥minprice)) } Listing 3: CSP of Search operation in Listing 2. 1C={//AllOrNone(location, radius); 2((locationSet==true =⇒radiusSet==true) AND 3(radiusSet==true =⇒locationSet==true) AND 4(¬locationSet==true =⇒ ¬radiusSet==true) AND 5(¬radiusSet==true =⇒ ¬locationSet==true)) AND 7 Mapping from IDL to CSP API Parameters CSP Mapping [Parameters] P∀pi∈P,      V←V∪pi∪piSet D←D∪domain(pi)∪Boolean C←C∪piSet == true (if piis required) IDL Element CSP Mapping Terms: map(T) [Parameter] piC←C∪ {piSet == true} [Parameter-Value Relation] pirelOp?vC←C∪ {pirelOp v ∧piSet == true} Predicates: map(P) [Term] T map(T) [Dependency] D map(D) [Term AND Predicate] TAND PC←C∪map(T)∧map(P) [Term OR Predicate] TOR PC←C∪map(T)∨map(P) [NOT Predicate] NOT PC←C∪ ¬map(P) Dependencies: map(D) [Requires] IF PiTHEN PjC←C∪map(Pi) =⇒map(Pj) [Or] Or(P1, ..., Pn)C←C∪Wn i=1 map(Pi) [OnlyOne] OnlyOne(P1, ..., Pn)C←C∪ {∀n i=1,∀n j=1|i6=j, map(Pi) =⇒ ¬map(Pj)} [AllOrNone] AllOrNone(P1, ..., Pn)C←C∪ ∀n i=1,∀n j=1|i6=j, {map(Pi) =⇒map(Pj)} ∧ {¬map(Pi) =⇒ ¬map(Pj)} [ZeroOrOne] ZeroOrOne(P1, ..., Pn)C←C∪ {map(OnlyOne(P1, ..., Pn))}∨{Vn i=1 ¬map(Pi)} [Relational Dependency] pirelOp?pjC←C∪ {(piSet == true ∧pjSet == true) =⇒pirelOp pj} [Arithmetic Dependency] piarOppjarOp... pnrelOp?v C ←C∪ {(piSet == true ∧pjSet == true ∧... pnSet == true) =⇒(piarOp pjarOp ... pnrelOp v)} ? relOp ={<|== | 6=|≥|≤|>} arOp ={+| − | ∗ |÷} Table 1: IDL to CSP mapping. 6//Or(query, type); 7(querySet==true OR typeSet==true) AND 8//maxprice >= minprice; 9(((maxpriceSet==true) AND (minpriceSet==true)) =⇒ 10 (maxprice ≥minprice)) } Listing 4: Constraints of Query operation in Listing 2. 1C={//OnlyOne(maxheight, maxwidth); 2((maxheightSet==true =⇒ ¬maxwidthSet==true) AND 3(maxwidthSet==true =⇒ ¬maxheightSet==true)) } Listing 5: Constraints of Get operation in Listing 2. 4.2 Analysis Operations In this section, we propose a catalogue of seven analysis operations on IDL specifications. These operations leverage the formal description of the dependencies using IDL to extract helpful information such as identifying inconsistencies or checking whether an API call is valid or not. Analogous analysis operations have been defined in the context of the automated analysis of feature models [3] and service level agreements [27], [28]. We may remark that it is not our intention to propose an exhaustive set of analysis operations as that would exceed the scope of this article. For the description of the operations in CSP, we will refer to the input IDL specification of an API operation IDL and the list of the parameters of the API operation P, taken from the API specification. Note that Pis necessary since it contains the information about the types of the parameters, and whether each parameter is defined as required or optional in the API specification. Additionally, we will use the following auxiliary operations: •map(IDL,P). This operation translates an input IDL specification IDL and the list of parameters Pfrom the API specification to a CSP following the mapping described in Section 4.1. •solve(CSP). This standard CSP-based operation returns a random solution for the input CSP (if any). •solveAll(CSP). This standard CSP-based operation returns all the solutions of the input CSP (if any). •filter(CSP,L). This operation takes as input a CSP and a list Lof pairs variable-value to be set, {{p1, v1},{p2, v2},...,{pn, vn}}, and returns the input CSP with additional constraints setting each variable in L,pi, to its corresponding value vi, i.e., C←C∪ {pi=vi}. 8 In what follows, for each operation, we provide a name, a description, an example, and an explanation of how it is mapped to a CSP. Consistent specification. This operation receives as input the IDL specification of an API operation and its list of parameters, and returns a Boolean indicating whether the specification is consistent or not. An IDL specification is consistent if there exists at least one request satisfying all the dependencies of the specification. Inconsistent specifications are the result of users’ mistakes and therefore automating their detection can be very helpful. This operation can be translated to a CSP as follows: isConsistentIDL(IDL,P) ⇐⇒ solve(map(IDL,P)) 6=∅ Dead parameter. This operation receives as input the IDL specification of an API operation, its list of parameters, and the name of a parameter, and it returns a Boolean indicating whether the parameter is dead or not. A parameter is dead if it cannot be included in any valid call to the service. Dead parameters are caused by inconsistencies in the specification or the design of the service. They may be hard to detect when the inconsistency is caused by several inter-related dependencies. For example, in the following IDL specification, the parameter p1 is dead since both constraints cannot be satisfied at the same time. 1IF p1 THEN p2; 2OnlyOne(p1, p2); Given an input parameter p, this operation can be automated by setting the CSP variable representing the presence of pto true (pSet =true) and checking whether the problem has at least one solution. If there is no solution, it means that pis dead, namely: isDeadParameter(IDL,P,p) ⇐⇒ solve(filter(map(IDL,P),{{pSet,true}})) = ∅ False optional. This operation assumes that the specification of each parameter indicates, as in OAS, whether the parameter is required (i.e., it must be included in every service request) or optional. This operation takes as input the IDL specification of an API operation, its list of parameters, and the name of a parameter specified as optional, and returns a Boolean indicating whether the parameter is false optional or not. A parameter is false optional if it is required (i.e., it must be included in all API calls to satisfy inter-parameter dependencies) despite being defined as optional. False optional parameters should be avoided since they give the user a wrong idea of the domain. For example, suppose that the parameter p1 is defined as mandatory (e.g., “required”: true in OAS) and p2 is declared as optional (“required”: false). The constraint “IF p1 THEN p2” in IDL would make p2 a false optional parameter. Given an input parameter specified as optional p, this operation can be automated setting the CSP variable representing the presence of pto false (pSet =false) and checking whether the problem has at least one solution. If it has no solutions, pis false optional. Note that the input IDL specification should be consistent, otherwise all parameters would be classified as false optional. This operation can be translated to a CSP as follows: isFalseOptional(IDL,P,p) ⇐⇒ isConsistentIDL(IDL,P) ∧ solve(filter(map(IDL,P),{{pSet,false}})) = ∅ Valid specification. This operation receives as input the IDL specification of an API operation and its list of parameters, and returns a Boolean indicating whether the specification is valid or not. An IDL specification is valid if it is consistent (i.e., there exists at least one request satisfying all the dependencies of the specification) and it does not contain any dead or false optional parameters. This operation, defined as a composition of the previous ones, can be helpful to easily detect errors when editing service specifications. This operation can be translated to a CSP as follows: isValidIDL(IDL,P) ⇐⇒ isConsistentIDL(IDL,P) ∧ ∀pi∈P(¬isDeadParameter(IDL,P,pi) ∧¬isFalseOptional(IDL,P,pi)) Valid request. This operation takes as input the IDL specification of an API operation, its list of parameters, and a service request (i.e., a list of parameters and their values) and returns a Boolean indicating whether the request is valid or not. A service request is valid if it satisfies all the dependencies of the IDL specification. For example, the following is a valid request for the IDL specification depicted in Listing 6 : {p1=2,p2=5}. 1Or(p1, p2 AND p3); 2OnlyOne(p2, p3); Listing 6: Valid IDL specification. Let Rbe an input request, i.e., a list of parameters and their respective values. This operation can be translated to a CSP by (1) setting the CSP variables related to each parameter to the value indicated in R, (2) setting the CSP variables related to the presence of the parameters in R to true (RiSet =true), (3) setting the CSP variables related to the parameters not included in R to false (OiSet =false where O=P\R), and (4) checking whether the problem has at least one solution. If it has no solutions, it means that the request is not valid, namely: isValidRequest(IDL,P,R) ⇐⇒ O=P\R∧ solve(filter(map(IDL,P),R∪ {{R1Set,true},{R2Set,true},...,{RnSet,true} {O1Set,false},{O2Set,false},...,{OkSet,false}})) 6=∅ Valid partial request. This operation is analogous to the previous one but the input request is partial or incomplete, meaning that some other parameters should still be included to make it a full valid request. This operation returns a Boolean indicating whether the partial request is valid. A partial request is valid if it does not include any contradiction, i.e., it can be extended with new parameters to become a valid request. 9 Let Sbe a partial input request. This operation can be specified as a CSP as follows: isValidPartialRequest(IDL,P,S) ⇐⇒ solve(filter(map(IDL,P),S∪ {{S1Set,true},{S2Set,true},...,{SnSet,true})) 6=∅ Random request. This operation receives as input the IDL specification of an API operation and its list of parameters, and returns a random valid request for the operation. This operation can be automated by translating the IDL specification to a CSP and requesting the solver to find a random solution, namely: randomRequest(IDL,P) = solve(map(IDL,P)) Table 2 summarizes some of the potential applications of the proposed analysis operations. As illustrated, four out of the seven operations are intended to automatically identify errors in IDL specifications. Note that although the operations Consistent specification,Dead parameter and False optional are related, each of them addresses a specific type of inconsistency and therefore they are helpful to point the users towards the specific types of errors found in their specification. The operation Valid request has applications in testing and monitoring. For example, complex test data generators could use this operation to check whether the generated API requests are valid or not. Also, an API gateway supporting this operation could detect and monitor invalid calls without the need to redirect the request to the target service, providing faster responses and reducing the consumption of user quota. The operation Valid partial request may be helpful for the early detection of inconsistencies. For example, an interactive API documentation supporting this operation could warn the user about inconsistencies as soon as a dependency is violated, without having to wait until constructing the full request. Finally, the operation Random request, in combination with test data generators, can be very useful for testing of web services as shown in Section 6. Operation Applications Consistent specification Specification error detection Dead parameter Specification error detection False optional Specification error detection Valid specification Specification error detection Valid request Testing, monitoring Valid partial request Interactive documentation Random request Testing Table 2: Potential applications of the analysis operations. 5 TOOLING SUPPORT As a part of our contribution, we provide a set of tools supporting the specification and analysis of inter-parameter dependencies in web APIs, including an editor of IDL specifications, an extension for the OAS language and an analysis library supporting the integration of our approach into any external project. Together, these components make Figure 4: IDL Editor. our work readily applicable in practice and provide a reference implementation for future contributions on the topic. 5.1 IDL Editor and Parser We implemented IDL using Xtext [50], a popular framework for the development of programming languages and DSLs. Xtext takes a grammar as input and generates a complete set of tools as output, including a linker, a compiler, a parser and a fully-fledged editor supporting features such as code completion, type checking, syntax coloring and validation. A simplified version of the IDL grammar is provided in Listing 1, the full version is available as a part of the implementation of IDL [19] (and also on the supplemental material provided with this article [43]). Figure 4 depicts a screenshot of the editor, showing some of its capabilities: code completion, syntax coloring and error checking. The editor is based on Eclipse, but is compatible with any web browser or IDE supporting the Language Server Protocol [24]. 5.2 IDL4OAS: An OAS Extension In order to foster the adoption of our approach, we propose an extension of OAS for the specification of inter-parameter dependencies using IDL. We call this extension IDL4OAS. An OAS document describes a REST API in terms of the elements it comprises, namely paths, operations, resources, request parameters and responses. OpenAPI provides a way to add extra information that may not be supported natively. This information is included in custom properties that start with “x-”, called extensions. IDL4OAS is an OAS extension that allows to specify a set of IDL dependencies for each API operation. An extra property called “x-dependencies” must be added at the operation level, including the set of dependencies among the input parameters of the operation. Listing 7 shows an excerpt of an OAS document extended with IDL4OAS, corresponding to the Search operation from the Google Maps Places API (see Listing 2). As illustrated, the property “x-dependencies” has been added to the “GET /search” operation. This property is actually an array of elements, where each element represents a single dependency, therefore they must be preceded by hyphens, following the YAML syntax.