Based on the theoretical framework of the actor-network sociology of innovation developed by Michel Callon, Bruno Latour and John Law, this paper will focus on the controversy which has been raging in Europe, and particularly in France, since 2004 when Google launched its project of a digital library. This controversy has shed light on different visions of digital libraries which resulted in projects such as the Google Book Search, Gallica 2 in France and Europeana, the European digital library. The paper will identify the sociotechnical network which emerged in Europe at the time of the controversy. It consists of both human organisations (national libraries, national governments and supra-national institutions, professional associations, companies) and technical artefacts (image-and text-digitization, mass digitization, retrieval tools). The digital library is considered here as an innovation based on technological inventions. This controversy sheds light on the actors' strategic positions in the sociotechnical network. It is thus critical to examine it before the closure of the technical innovation inherent to this conflict.

Since the mid-nineties and the public dissemination of the world wide web, the circulation of cultural heritage on the internet has become an important challenge for libraries.

Countless conferences and congresses have been held to deal with this issue, numerous projects and case studies have been discussed in the librarian community. New services emerged at the turn of the century which are called digital libraries and are provided by various organizations, be they private-owned companies (Google), public-private partnerships (Open Content Alliance) or public institutions (national libraries).

Can we consider digital libraries as innovations ? Norbert [START_REF] Alter | L'innovation ordinaire[END_REF] made a distinction between invention and innovation using the definitions provided by Joseph Schumpeter (as cited in [START_REF] Alter | L'innovation ordinaire[END_REF]. According to the latter, an invention was the elaboration of new goods, new products, new methods of production, new technologies. An innovation was the integration in a given social environment of these very same inventions. Invention was an event, innovation was a process. There was no direct link between the quality of an invention and its dissemination. An invention had to be socially and economically successful to become an innovation.

Digital libraries are based on technologies like the internet protocol, 2D digitization, OCR, electronic storage facilities, servers, metadata, search and retrieval systems which were invented at the end of the twentieth century. The innovation called the digital library is still developing as a process. Digital libraries created by different institutions, though based on very similar technological bricks, are characterized by their high degree of interpretive flexibility, meaning that different innovators have their own idea of what a digital library should be. These actors -or actants according to the sociotechnical approach-and their relative position in the global network surrounding the innovation named the digital library can be identified when a controversy arises. This paper will study the controversy Google Inc. triggered when it launched its digitization project in 2004 to characterize a type of digital library which was born out of it.

This article comes within the scope of studies dealing with innovation in libraries.

They have taken into consideration various services ranging from the perceptions of the OCLC system among the member libraries of the Association of Research Libraries [START_REF] Luquire | Attitudes toward Automation/Innovation in Academic libraries[END_REF] to the rate of diffusion of digital reference services among 140 academic libraries in universities and colleges [START_REF] White | Diffusion of an innovation: Digital reference service in Carnegie Foundation Master's (comprehensive) Academic Institution Libraries[END_REF] or the link between strategy and innovation in libraries [START_REF] Deiss | Innovation and Strategy : Risk and Choice in Shaping User-centered Libraries[END_REF]. More recently, Marija [START_REF] Dalbello | Institutional shaping of cultural memory : digital library as environment for textual transmission[END_REF]Dalbello ( , 2005[START_REF] Dalbello | Cultural dimensions of digital library development, part 1 : Theory and methodological framework for a comparative study of the cultures of innovation in five European national libraries[END_REF][START_REF] Dalbello | Cultural dimensions of digital library development, part 2 : The cultures of innovation in five European national libraries (narratives of development)[END_REF] has published articles which are milestones for research about digital libraries. Her perspective is original as she combines document analysis and interviews as well as different theories, from institutional change and sociology of culture to the social construction of technology. This paper seeks to contribute to the history of digital libraries by focusing on a controversy out of which competing representations of the digital library have emerged.

Sources and Methodology

The corpus consists of written sources such as articles published by Le Monde, the Europe. The English version had a large impact in the USA [START_REF] Bearman | Jean-Noël Jeanneney's Critique of Google: Private Sector Book and Digital Library Policy[END_REF][START_REF] Darnton | Entretien avec Jean-Robert Dantou[END_REF].

Reports from the French government and the European Commission expressed the attitudes of official bodies during the controversy. The Google Press Center gives online access to all Google press releases. Those concerning Google Book Search and the subsequent legal battle with the U.S. publishing industry were of particular interest for this paper.

The theoretical framework for this study is based on the actor-network theory (ANT).

According to it, technology is contingent and shaped socially. The sociological, political, economic and historical circumstances have an influence on the process that leads to innovation. Before a technology is stabilized or comes to closure or is « blackboxed », it is taken amidst conflicting interests. « The pattern is that the protagonists -entrepreneurs, industrial or commercial organizations, government bureaucracies, customers or consumers, designers, inventors or professional practitioners-seek to establish or maintain a particular technology or set of technological arrangements and with this a set of social, scientific, economic and organizational relations. » (Bijker & Law, 1992, p. 8). M. [START_REF] Akrich | The De-scription of technical objects[END_REF] took up this idea of inscription: « like a film script, technical objects define a framework of action together with the actors and the space in which they are going to act. » (p. 208).

The actor is « an element which makes other elements dependent upon itself and translates their will into a language of its own » (Callon & Latour, 1981, p. 286). The actor « tells you what you want, what you will be able to do in 5, 10 or 15 years, in which order you will do it, what you will be glad to possess and of what you will be capable. And you really believe this, you identify with the actor and will help him or her with all your strength. » (id.

p. 288).

The actant, a material or human actor, is part of a global network, « a set of relations between an actor and its neighbors on one hand and between those neighbors on the other » (Callon & Law, 1992, p. 21) that must be distinguished from the local network which is « the development of an array of the heterogeneous sets of bits and pieces that is necessary to the successful production of any working device. » (Callon & Law, 1992, p. 21). There must be a/some link(s) between the two networks, known as « obligatory passing point(s) » (Callon & Law, 1992, p. 46), for the project to succeed.

Heterogeneous actors belonging to a global network can reach an agreement to promote an innovation thanks to the concept of translation. « By translation we understand all the negotiations, intrigues, calculations, acts of persuasion and violence, thanks to which an actor or force takes or causes to be conferred on itself authority to speak or act on behalf of another actor or force. » (Callon & Latour, 1981, p. 279). Four steps are necessary to build a network : "problématisation" (the main actor defines the problem), "intéressement" (the main actor seeks allies), enrolment (the various actors take the stage) and mobilisation (the main actor entices the others to act). Both authors stress the importance of the controversy which is the expression of the translation process.

ANT heavily relies on innovation case studies, be it an aircraft, fluorescent lighting or scallop industry. [START_REF] Hanseth | Understanding Information Infrastructure[END_REF] used ANT to study the emergence of information infrastructures such as the internet and the Norwegian health care network and demonstrated that this theory was particularly relevant to their purpose since it was « more specific and concrete with respect to the functions of an IS [information system] » (chapter 6: Socio-technical webs and actor network theory, para. 34). They favored ANT more than the structurational model of technology devised by [START_REF] Orlikowski | The Duality of Technology: Rethinking the Concept of Technology in Organizations[END_REF] or the social construction of technology (SCOT). This paper will follow the same approach considering the digital library as an information system. Nevertheless, the aforementioned theories can also be used to study innovation in libraries [START_REF] Dalbello | Cultural dimensions of digital library development, part 2 : The cultures of innovation in five European national libraries (narratives of development)[END_REF].

The Constitution of a Network: the Controversy about the Digital Library (2004)(2005)(2006)(2007)(2008)(2009)

Context Analysis

The controversy about the digital library has been growing within a specific context since 2004. M. Dalbello studied the emergence of digital libraries from 1997 onwards in the USA and compared them to « cabinets de curiosité in their limited ability to support scholarship or address information needs of defined community users » (Dalbello, 2004, p. 265). This period was characterized in the USA by pilot project policies as far as digitization was concerned. It was also the case in France where funding had been allocated by the Ministry of culture for the digitization of special collections belonging to various memory institutions. The latter had submitted projects in response to regular calls for proposals since 1998. The European Commission had also adopted this approach. Therefore, the period from the mid-1990s until 2002 could be identified as « the first wave of digital library development in Europe » (Dalbello, 2008, p. 391).

During this first phase, digitized materials mostly belonged to the public domain.

Though the French national library (BnF) had digitized copyrighted materials, it did not reach an agreement with publishers to give online access to these documents when the new building opened to the public. Apart from publishers specialized in sciences and law, who had created their own database services or signed contracts with online vendors, publishers specialized in literature, and especially the French ones, were at that time very reluctant to digitize their collections and go online (Bibliothèque nationale de France, 2006).

The Google company was created in September 1998 : at that time, its main product was « a large-scale search engine which makes heavy use of the structure present in hypertext » [START_REF] Brin | The Anatomy of a Large-Scale Hypertextual Web Search Engine[END_REF]. On Aug. 19th, 2004, Google entered the stock market (NASDAQ) and launched an initial public offering, quickly raising 1,7 billion dollars. The company was thus in a position to invest massively and undertake new projects.

The Sociotechnical Network in Progress

During a press briefing at Frankfurt Book Fair in October 2004, Google Inc.'s two founders unveiled the Google Print Program which was developed to scan books published by Penguin, Hyperion, Scholastic, Houghton Mifflin and some university presses with which Google Inc. was still negotiating. A user would perform a Google search and books containing the search term would show up among the search results. The user could browse only two pages backward and forward from any page where the search term appeared. At that time, some publishers had signed an agreement with Google Inc. which was similar to the one they already had with Amazon.

Two months later, Google Inc. announced a second project: the company was to digitize the entire collections of five world-class libraries, namely the University of Digital library as a controversy Michigan's, Harvard's, Stanford's, Oxford's and the New York Public Library. The company was eager to offer out-of-print material that only libraries kept.

O'Sullivan and Smith (2004) stated:

We launched the first part of Google Print in October to make the world of books more discoverable. The thing is, most books in the world are out of print. By working with libraries as well as publishers, we'll have access to millions of books, including many unique volumes that haven't been read in years. Soon a new generation will be to discover them too. (para. 3) Though libraries and publishers were supposed to work together with Google Inc. in harmony, the Library Digitization Plan caused publishers to react defiantly and to sue the company for massive copyright infringement in October 2006. Publishers were concerned by the fact that Google Inc. had not cleared the copyright prior to digitizing the libraries' collections and that the opt-out system required publishers to monitor the digitizing process Referring to ANT's terminology, Jeanneney acted as the « translator ». This « actant » is the focus point of the network: Jeanneney made an analysis of Google's strategy and voiced his critiques which were taken seriously by other « actants » because he had the legitimacy to do so. Jeanneney's family belongs to the so called « noblesse d'État » as described by Pierre [START_REF] Bourdieu | La noblesse d'État : grandes écoles et esprit de corps[END_REF]. Jules Jeanneney, Jean-Noël Jeanneney's grandfather, was president of the French Senate from 1932 to 1944. Jean-Marcel Jeanneney, Jean-Noël Jeanneney's father, was appointed minister of industry in 1959 and subsequently held various public offices. Jean-Noël Jeanneney himself was secretary of state for trade (1991)(1992) and for communication (1992)(1993)). An alumnus of the Ecole normale supérieure, he is also a university professor and a historian of the media.

As the president of the French national library from 2002 to 2007, he also had legitimacy conferred upon him by the institution and the Gallica experiment. The French national library was created by King Louis XI during the 15 th century. Since 1537, the library has managed French legal deposit for books (and later, for other materials) in order to create a collection and to preserve it. At that time, Gallica, the French encyclopaedic digital library, held 80000 image-digitized books and 70000 digitized pictures. This digital library was the cornerstone of the new national library officially launched by President François Mitterrand in 1988 who had conceived of « a totally new kind of library » (as cited in [START_REF] Stasse | La véritable histoire de la grande bibliothèque[END_REF]. Along his own words, this new library was supposed to be « the biggest and the most modern library of the world » that embodied what « France was able to achieve » (as cited in [START_REF] Bouchard | Des puces, des livres et des hommes : la numérisation des imprimés à la Bibliothèque nationale de France[END_REF]. Hence the symbolical and political importance of the new library and the legitimacy of its president Jeanneney.

What were Jeanneney's main criticisms against Google's project which have triggered the coalescence of the actants of the sociotechnical network which gathered around the French project of a digital library? They ranged from political reflections to cultural and technical remarks.

Being a member of the « noblesse d'État », Jeanneney quoted Charles de Gaulle in his book: « The market is not above the nation and the State. The State and the nation must dominate the market. » (as cited in Jeanneney, 2006, p. 49). Jeanneney criticized Adam Smith's liberalism and advocated state regulation. Google had taken advantage of the fact that the American federal state did not interfere with the internet apart from domain names regulations. This point of view was shared by Robert Darnton, who was appointed librarian at Harvard university in 2007 : « While the public authorities slept, Google took the initiative. » [START_REF] Darnton | Google & the Future of Books[END_REF].

According to Jeanneney (2006), Google was only interested in digitizing Englishlanguage resources and did not abide by the UNESCO declaration about cultural diversity.

The European states and the European Commission should be concerned about Google's project since it excluded multiculturalism. The Google's project's main goal was to generate profit through targeted advertisement and to have private companies pay for the digitization.

The results ranking on Google Book Program search page would be biased because of advertisement. Moreover, Jeanneney made a distinction between retrieving web pages and retrieving whole books: in the latter case, bibliographic data should be provided automatically in order to define the context of the book.

The book is the only medium that has remained free of any advertisement until now and Jeanneney would like to preserve the status quo. According to him, the agreement between Google and the five libraries was unbalanced since these libraries had, for some time, been acquiring and preserving their collections by investing massively. Comparatively Google was investing less in digitizing books since it recuperated its money via advertisement.

Furthermore, Google could disappear or be sold to another company : what then would become of all digitized information ? Jeanneney stated that Google was not an archival trustee but a commercial entity that did not care about long term preservation. « Heritage preservation is the core activity of public institutions which public authorities subsidize with money ensuring constant or increasing budgets. » (Jeanneney, 2006 p. 112) Jeanneney did also make a few proposals and then again he played the role of the translator. He was in favour of a cooperative action between libraries and other memory institutions, such as archives and museums, sustained by public money, to build a European digital library. The collections would be selected along the following criteria: encyclopaedias, core texts of the European civilisation, journals of scholarly societies, studies about democracy, law and European integration, landmark publications in the fields of literature, science, law, economics and arts. Commercial publishers were invited to take part in the venture by providing their copyrighted collections. This was the cultural project defended by Jeanneney who also supported the creation of a European search engine. Only at the very end of his book did Jeanneney mention the public of this digital library consisting mainly of journalists, scholars and students. The digital libraries initiative aims at enabling all Europeans to access Europe's collective memory and use it for education, work, leisure and creativity. The efforts in this area will contribute to Europe's competitiveness and will support Union action in the field of culture:

-The online presence of material from different cultures and in different languages will make it easier for citizens to appreciate their own cultural heritage as well as the of other European countries. The recommended measures will contribute to presenting Europe's rich and diverse heritage on the Internet and to protecting cultural assets from irretrievable loss.

Beyond its fundamental cultural value, cultural material is an important resource for new added value services. The measures recommended will contribute to enhancing growth in related high value-added sectors such as tourism, education and media.

High-quality digital content is a key driver for large scale industrial activities (hence the interest on the part of major search engines). Digitisation and digital preservation are knowledge-intensive activities that are likely to grow considerably in the coming years.

The European Commission seemed to have endorsed the analysis of Jeanneney and joined the global network while supporting digital cultural diversity, long term preservation and European industrial development based on digital contents. It urged member states to contribute to the European digital library. On July 12 th , 2005, the French government issued a decree creating a working group about the European digital library. This working group published a report the following year [START_REF] Lesquins | Bibliothèque numérique européenne: rapport de synthèse et plans d'action[END_REF] in which the European Commission's wait-and-see policy was criticized (p. 59). The French national library set up a prototype digital library called Europeana which was tested with 550 users in 2006 and 2007 (Ourouk, 2006[START_REF] Lesquins | Europeana : rapport de bilan sur les usages et les attentes des utilisateurs d'Europeana[END_REF] Sept. 2006 andFeb. 2007. French publishers were invited to take part in the European digital library and were offered some state funding to start digitizing their back catalogue. These subsidies, coming from a tax on copy machines, have been managed by the Centre national du livre (CNL). French online book vendors (Cyberlibris, Documentation française, Edilivre, Editis, Numilog and Tite-Live) were also called upon to outline a business model for copyrighted materials available on Gallica 2. As the French national library is responsible for the legal deposit of books, it has sustained business contacts with publishers for a long time. That has proved to be a definite advantage.

Relying on the support that the French President had given to him, Jeanneney and the ANT considers technical artefacts as actants of the network. It has to be kept in mind that Google was first of all a search engine that did full text indexing of Web pages, i.e. content which was not copyrighted. Before 2004, Google Inc. had not dealt with copyrighted material. The naïve tone of the announcement made by O'Sullivan and Smith was marked with the utopia of the universal library and at that time Google Inc. might have overlooked the problem of intellectual property rights. Gallica 1 was a digital library built upon an automated library catalogue: document retrieval was based on traditional MARC metadata for most digitized items. Google's initiative forced the French national library to contemplate mass full-text digitization of documents and thus modify the structure of Gallica to achieve Gallica Discussion This paper focuses on the French side of the controversy spinning around the digital library. The ANT could also be used to analyse the controversy which has taken place in the USA. Google Inc.'s global network, though it was threatened for a while by the legal action led by publishers, has gained some strength thanks to the libraries which have joined the project. To date, 20 libraries from different countries are part of the project. Google Inc. has become committed in promoting multiculturalism and the advanced search facility permits users to select the language of the books to retrieve. The agreement which the company reached with authors and publishers in Oct. 2008 can be considered as the obligatory passing point Google Inc. had to go through to enlarge its network. However, the article published by Robert [START_REF] Darnton | Google & the Future of Books[END_REF] shows that the controversy is not dead and that the network is not yet stabilized on the libraries' side.

The advent of the product called Google Book Search is a sign of the industrialization of memory which has challenged the traditional actors of its management like archives, libraries and museums [START_REF] Merzeau | Mémoire[END_REF]. A company has the means to question the concept of cultural imperatives defined by Greg Urban (as cited in [START_REF] Dalbello | Cultural dimensions of digital library development, part 1 : Theory and methodological framework for a comparative study of the cultures of innovation in five European national libraries[END_REF] and the prominent role played by national libraries in the definition of « authoritative representations of cultural heritage » [START_REF] Dalbello | Cultural dimensions of digital library development, part 2 : The cultures of innovation in five European national libraries (narratives of development)[END_REF]. Memory seems to evolve from a pyramidal structure to a rhizome-like one [START_REF] Merzeau | Mémoire[END_REF] in which various actors interfere, large companies but also individuals. Rather than being a threat, this scattered structure appears to some as the ultimate decentralized memory institute [START_REF] Uricchio | Moving beyond the artifact : lessons from participatory culture[END_REF]. This paper does not take into account the positions of the various groups of users. As Gallica 2 and Google Book Search are turned into « black boxes » and submitted to the users' appreciation, it would be stimulating to further study their reactions to these innovations. M. [START_REF] Akrich | The De-scription of technical objects[END_REF] chose this approach when studying a photoelectric lighting kit created by European engineers and implemented by African end users. In this case, sources may range from market surveys and interviews to blogs and mailing lists. As Gallica 2 has just celebrated its first anniversary, a user survey has been released which advocates its continuation [START_REF] Ourouk | Synthèse de l'étude d'évaluation de l'expérimentation de la mise à disposition d'ouvrages sous droits via la bibliothèque numérique de la BnF Gallica 2[END_REF].

French

  newspaper of reference, between 2005 and 2009, and articles published by various English-speaking newspapers between 2005 and 2009. The paper also makes extensive use of the book Quand Google défie l'Europe published in 2005 by Jean-Noël Jeanneney, then the director of the Bibliothèque nationale de France. This volume was an expanded version of the editorial « Quand Google défie l'Europe » (When Google challenges Europe) which appeared in Le Monde on Jan. 23rd, 2005. A second edition of the book was released in Sept. 2006 in France. Soon afterward, it was translated to English and published by the University of Chicago Press under the title Google and the Myth of Universal Knowledge : a view from

  would have been costly and work-consuming. Jean-Noel Jeanneney, then the president of the Bibliothèque nationale de France, published his two-page long editorial entitled « Quand Google défie l'Europe » on Jan. 23rd, 2005 in the elite French newspaper Le Monde. In April 2005, he published a book with the same title. A new edition was issued in 2006 with an introduction entitled Chronicle of a battle.

  Jeanneney's book can considered as the obligatory passing point around which the global network has been forming itself attracting European national and community leaders, administrations, traditional publishers, online book vendors and R&D companies and media. The book has been translated into English, Arabic, Chinese, German and Portuguese, thereby enlarging its impact. President Jacques Chirac, who claimed the heritage of de Gaulle, had an interview with Jeanneney and the French minister of culture on March 16th, 2005, six weeks after the publication of Jeanneney's article in Monde. On April 28th, six European political leaders (France, Germany, Hungary, Italy, Poland, Spain) signed a letter addressed to the Presidents of the European Council and of the European Commission in which they commended the digitization of the European cultural heritage which had to « keep its rank in the future organisation of knowledge ». In April as well, 19 European national libraries signed a motion claiming for a financial support from the European Commission to create the European library (Roux, 2005). But, this very same year, the British Library decided to sign an agreement with Microsoft's MSN Book search to digitize around 100,000 out-of-copyright books. Rather than joining the European coalition, it favored another network, the Open content alliance. The President of the European Commission replied positively to the six presidents' letter and the Council of the European Union subsequently endorsed the objectives of i2010-A European Information Society for growth and employment. A recommendation on the digitisation and online accessibility of cultural material and digital preservation was issued by the Commission of the European Communities (2006):

  . Only two European national libraries, Hungary and Portugal, took part in the project developed by the BnF. In 2008, the prototype was given to the EDL Foundation in charge of creating the European digital library. Meanwhile in the USA, Google Inc. was forced to stop its digitization program in August 2005 due to the reaction of the Association of American Publishers and the Authors' Guild which both sued Google for digitizing copyrighted material pertaining to the libraries' collections. French publishers, represented by the Syndicat national de l'édition (SNE), also started a legal action against Google in 2006: they did not want to acknowledge the « optout » possibility according to which Google could digitize copyrighted books as as publishers had not express their disagreement. Two official reports, sponsored by the French Ministry of culture and published respectively in 2005 and 2007, stressed the importance of copyrighted material that should be offered by the European digital library along with public domain collections. The first report, written by François Stasse, former director of the French national library (1998-2001), defined a « grey zone » of copyrighted materials belonging to publishers' back catalogue. These titles are no longer profitable to publishers and digitisation would open a new market. The second report, entitled Book 2010, was the result of a series of eleven workshops which took place between

French

  national library were able to rally several actors to form what can be called a global network: public administrations depending on the Ministry of culture, European authorities and publishers have all contributed to the creation of Gallica 2. The French national library has thus been able to create local networks to eventually set up its vision of the digital library. Digital library as a controversy In 2007, the French national library signed a three-year contract with SAFIG S.A. to digitize 100,000 new items each year, in text and image mode. Since March 2008, search has been possible for several thousand copyrighted books available in digital format via e-retailers' websites (with free or controlled access). The Quaero consortium, led by the companies Thomson, France Telecom, Jouve and Exalead, was launched in March 2008 after the European Commission authorised aid of €99 million to France for this R&D programme. Its aim is to develop a new search engine to index and retrieve digital media. The participation of the French national library in European projects such as IMPACT is also a way to enlarge the local network around its vision of the digital library.

Acknowledgements

The author wishes to express her gratitude to Pr. Catherine Bertho-Lavenir, Université Paris III Sorbonne nouvelle, for her inspiring advice.


Julien Henry

David Monniaux

Matthieu Moy

PAGAI: a path sensitive static analyzer

We describe the design and the implementation of PAGAI, a new static analyzer working over the LLVM compiler infrastructure, which computes inductive invariants on the numerical variables of the analyzed program.

PAGAI implements various state-of-the-art algorithms combining abstract interpretation and decision procedures (SMT-solving), focusing on distinction of paths inside the control flow graph while avoiding systematic exponential enumerations. It is parametric in the abstract domain in use, the iteration algorithm, and the decision procedure.

We compared the time and precision of various combinations of analysis algorithms and abstract domains, with extensive experiments both on personal benchmarks and widely available GNU programs.

Introduction

Sound static analysis automatically computes properties on programs, such as the possible values of their variables during execution. Applications include: showing that a program cannot encounter a runtime error (such as arithmetic overflow, division by zero, array access out of bounds), as in e.g. the Astrée analyzer [START_REF] Cousot | The ASTR ÉE analyzer[END_REF]; computing invariants for use with assisted proof systems (such as the B method [START_REF] Moy | The B-Book: Assigning Programs to Meanings[END_REF]), thereby lessening the burden on the user; computing invariants for advanced optimization techniques in compilation (e.g. showing that two array cells are distinct, in order to allow instruction reordering between assignments to these cells). All these applications need invariants on numerical quantities.

This article introduces PAGAI, a new tool for fully automatic static analysis. PAGAI takes as input a program in the "bitcode" intermediate representation of LLVM [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis & transformation[END_REF][START_REF]LLVM team[END_REF], a modern compilation framework. LLVM bitcode is a target for several industrial-strengh compilers, most notably Clang (supporting C, C++, Objective-C and Objective-C++) and llvm-gcc (supporting, in addition to these, Fortran and Ada); furthermore, a growing number of analysis tools, testing tools, etc. are currently built around this platform (Calysto, KLEE, LAV, LLBMC).

The output of PAGAI is a list of inductive invariants for a selected subset of the control nodes of the original program: for structured source programs, PAGAI will provide an inductive invariant for loop headers. 1At present, PAGAI checks user-specified safety properties provided through assertions using the standard C/C++ assert (condition) macro. The tool will attempt proving that the assertion failure is unreachable and, if unsuccessful, provide a warning message (the tool does not at present include bounded model checking or path exploration techniques for reconstructing an actual failure trace, thus such a warning message should be interpreted as a possible assertion failure). It also allows user-specified assumptions, through the assume(condition) macro. Executing traces falsifying assertions or assumptions are considered to terminate when executing the macro; thus, user-specified assertions may be used to guide the analyzer by providing invariants that it was not able to synthesize by itself. Possible extensions could include checking for memory safety of array accesses.

PAGAI is based on abstract interpretation, a general framework for fully automatic static analysis. PAGAI infers invariants of a selected form; by default it performs linear relation analysis, which obtains invariants as conjunctions of linear inequalities (or, equivalently, convex polyhedra), but it also supports other abstract domains through a runtime option. Depending on the iteration algorithm selected, PAGAI may also infer invariants as disjunctions of elements of the abstract domain (e.g. unions of convex polyhedra).

Textbook descriptions of abstract interpretation-based static analysis state that an inductive invariant is computed at every control point of the program. In contrast, PAGAI abstracts straight-line sequences of statements en bloc, computing invariants only at points where control flow branches or merges. Furthermore, several algorithms implemented in PAGAI compute invariants only at the heads of loops (or, in general control-flow graph, at nodes forming a feedback vertex set, whose removal breaks all cycles in the graph), expanding the rest of the control flow to a possibly exponential number of straight-line sequences of statements between the selected nodes. In order to avoid explicit enumerations of exponential sets, PAGAI uses decision procedures for arithmetic theories, based on the satisfiability modulo theory (SMT) approach: each path is enumerated only if needed, in response to a positive satisfiability query [START_REF] Henry | Succinct representations for abstract interpretation[END_REF][START_REF] Monniaux | Using bounded model checking to focus fixpoint iterations[END_REF].

The PAGAI tool is dedicated to experimenting with new analysis algorithms. It allows independent selection of the abstract domain and the iteration strategy, and partially independent selection of decision procedure, 2 and thus is well-suited for comparisons. We thus conducted extensive experiments both on examples we produced ourselves (sometimes inspired by industrial code) and on GNU programs, for which the ability to run on any C or C++ code, through the LLVM system, was especially useful. Front-ends for many analysis tools put restrictions (e.g. no backward goto instructions, no pointer arithmetic...), often satisfied by safety-critical embedded programs, but not by generic programs; our tool suffers no such restrictions, though it may in some cases apply coarse abstractions which may possibly yield weak invariants.

After illustrating the limitation of traditional abstract interpretation on an example in section 2, we will describe PAGAI's implementation in section 3, and comment on the results of extensive experiments in section 4, allowing the comparison of state of the art techniques on real-life programs.

Motivating Example

In most forward abstract interpretation-based analyses, when control flows from several nodes into a single node, the abstract value at that node is obtained by computing the least upper bound of the incoming abstract values in the abstract domain (in backward analysis, this occurs when control flows from a single node to several nodes). If the abstract domain is convex polyhedra, then this means computing the convex hull of the incoming polyhedra. Such an operation may induce unrecoverable loss of precision by introducing spurious states that cannot occur in concrete program runs.

An example of program where such a loss of precision occurs is depicted in Fig. 1. In this program, the loop body has two feasible paths that are executed alternatively, depending on a variable "phase". Such programs, with active code paths depending on global "mode" or "phase" variables, often occur in reactive systems.

Removing program point n 0 breaks all cycles; we are thus primarily concerned with obtaining an inductive invariant at that point. We consider the domain of convex polyhedra and thus wish to obtain this invariant as a polyhedron. Because convex polyhedra form a lattice of infinite height, we use Kleene iterations (pushing abstract values through control-flow edges) with a widening scheme, which ensures convergence in finite time to an inductive invariant, followed by decreasing (narrowing) iterations.

At program point n 5 , classical forward abstract interpretation with convex polyhedra computes the convex hull of three incoming polyhedra over variables (phase, x, t). This convex hull introduces extra states, unreachable in the concrete programs, for the analysis of the fragment from n 5 to n 9 . When analyzing the whole loop, these extra states prevent proving x < 100.

To cope with this problem, a solution is to compute disjunctive invariants at all intermediate nodes: at n 5 , keep an explicit list of three polyhedra, and thus obtain a list of nine polyhedra at n 9 . We pass the convex hull of these polyhedra to the widening operator at point n 0 (which operates on polyhedra, not on lists of polyhedra). The drawback is that the number of elements in the lists may grow exponentially with the number of successive tests.

A second solution, equivalent to the preceding with respect to final results but different in its operation, is to distinguish all nine paths inside the loop (from n 0 to n 0 ), compute the final outcome of each path, and compute the convex hull of these outcomes. Instead of enumerating all nine paths explicitly, we consider them in succession, only as needed. We start with an empty polyhedron at n 9 (more generally, it should contain initial states at this control point), and process paths as long as they make this polyhedron grow. The next path to consider is obtained from a model of an arithmetic formula expressing this growth condition [START_REF] Monniaux | Using bounded model checking to focus fixpoint iterations[END_REF]; if this formula is unsatisfiable, this means there is no such path and thus the convex hull encompasses the outcome of all paths. The advantages of this second method over the preceding one are twofold: there is no exponentially large list of abstract elements, and the satisfiability query for the formula is handed over to a satisfiability modulo theory (SMT) solver. Modern SMT-solvers are very efficient; their caching mechanisms may, for instance, remember that taking a certain branch in the code is incompatible with taking another one (if a Boolean is associated with passing through each branch, then this is just a blocking clause inside the underlying SAT-solver). The algorithms implemented in PAGAI are variants of this approach of implicitly representing of exponentially-sized sets of paths and enumerating them as needed.

i n t x = 0 ; i n t t = 0 ; i n t phase = 0 ;

while ( t < 1 0 0 ) { i f ( phase == 0 ) x = x + 2 ; i f ( phase == 1 ) x = x -1; phase = 1-phase ; t ++; } a s s e r t ( x <= 1 0 0 ) ; n n 0 n f n 1 n 3 n 2 n 4 n 5 n 7 n 6 n 8 n 9 x ← 0 phase ← 1 t >= 100 t < 100 phase, 0? < > = x ← x + 2 phase, 1? < > = x ← x -1 phase ← 1 -phase t ← t + 1

Implementation

PAGAI is a prototype interprocedural static analyzer, that implements our recent combined techniques [START_REF] Henry | Succinct representations for abstract interpretation[END_REF] as well as the classical abstract interpretation algorithm, and the state-of-the-art techniques Path Focusing [START_REF] Monniaux | Using bounded model checking to focus fixpoint iterations[END_REF] and Guided Static Analysis [START_REF] Gopan | Guided static analysis[END_REF]. Abstract domains are provided by the APRON library [START_REF] Jeannet | Apron: A library of numerical abstract domains for static analysis[END_REF], and include convex polyhedra (from the builtin Polka "PK" library), octagons, and products of intervals. It also has an interface with the Parma Polyhedra Library [START_REF] Bagnara | The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems[END_REF], giving access to more abstract domains (e.g. a reduced product of polyhedra and linear congruences, producing invariants such as 0 ≤ x ≤ 1001 ∧ x ≡ 0 (mod 7)).

For SMT-solving, our analyzer uses Yices [START_REF] Dutertre | A fast linear-arithmetic solver for DPLL(T)[END_REF] or Microsoft Z3 [START_REF] De Moura | Z3: An efficient SMT solver[END_REF] through their C API. An implementation of communications with the SMT-solver by textual messages sent through a pipe following the SMT-Lib 2 standard [START_REF] Barrett | The SMT-LIB Standard: Version 2.0[END_REF] is underway, and now partially supports Z3, MathSAT 5 and SMTinterpol. 3

Analysis algorithm

For each program, we distinguish a set P W of suitable widening points by a simple algorithm: initialize P W = ∅ and for each procedure, compute the strongly connected components of its control-flow graph using Tarjan's algorithm; the targets of the back-edges of the depth-first search are added to P W . The resulting cut set or feedback vertex set is not necessarily minimal, but is sufficient to disconnect all cycles -more sophisticated techniques are discussed in e.g. Bourdoncle [START_REF] Bourdoncle | Sémantiques des Langages Impératifs d'Ordre Supérieur et Interprétation Abstraite[END_REF]. 4 It is however unclear whether more advanced selection tech-niques would finally yield stronger invariants; the current simple scheme has the advantage that, when run over a control-flow graph obtained from a structured program, it marks heads of loops, which is a "natural" choice.

While [START_REF] Henry | Succinct representations for abstract interpretation[END_REF][START_REF] Monniaux | Using bounded model checking to focus fixpoint iterations[END_REF] provide for another set P R ⊇ P W , with abstract join operators (as opposed to widenings) being applied at points in P R \ P W , our tool does not currently such technique, which is meant to reduce the complexity of SMT formulas at the expense of analysis precision.

LLVM bitcode is in static single assignment (SSA) form: a given scalar variable is given a value at a single syntactic point in the program. In concrete terms, an assignment x=2 * x+1; gets translated into a definition x 2 = 2x 1 + 1, with distinct variables x 1 and x 2 corresponding to the same original variable x at different points in the program. Because LLVM generally assigns rather straightforward names (e.g. x.0 for the first renaming of variable x), the user can map the invariants back to the original source code; an automatic and more robust back-to-source mapping, based on debugging information, is being developed.

LLVM makes it easy to follow definition-use and use-definition chains: for a given variable (say, x 2 ) one can immediately obtain its definition (say, 2x 1 + 1). One may see conversion to SSA form as a static precomputation of some of the symbolic propagations proposed by Miné [START_REF] Miné | Symbolic methods to enhance the precision of numerical abstract domains[END_REF] to enhance the precision of analyses.

SSA introduces φ-functions at the head of a control code to define variables whose value depends on which incoming edge was last taken to reach this control node. For instance, for if (...) { x = 2 * x+1; } else { x= 0; }, then x 2 is defined as φ(2x 1 + 1, 0).

In this framework, each variable is uniquely defined as an arithmetic (+, -, ×, /) function of other variables that themselves may not be representable as arithmetic functions, because they are defined using φ-functions, loads from memory, return values from function calls, or other numerical operations (e.g. bitwise operators) that are not representable with our class of basic arithmetic operations. We may vary the class of arithmetic operations, for instance, by restricting ourselves to linear ones.

This motivates a key implementation decision of our tool: only those variables v 1 , . . . , v n that are not defined by arithmetic operations are retained as coordinates in the abstract domain (e.g. as dimensions in polyhedra), assuming they are live at the associated control point.

For instance, assume that x, y, z are numerical variables of a program, x is defined as x = y + z, and x, y, z are live at point p. Instead of having x as a dimension for the abstract value at point p, we only have y and z. All the properties for x can be directly extracted from the abstract value attached to p and the relation x = y + z. This is an optimisation in the sense that there is redundant information in the abstract value if both x, y and z are dimensions of X p . The classical definition of liveness can be adapted to our case:

problem, but Shamir [START_REF] Shamir | A linear time algorithm for finding minimum cutsets in reducible graphs[END_REF] showed that it can be done in linear time for a class of graphs including reducible graphs, that is, those obtained from structured programs. This latter algorithm is being implemented.

Definition 1 (Liveness by linearity). A variable v is live by linearity at a control point p if and only if one of these conditions holds: (i) v is live in p.

(ii) There is a variable v ′ , defined as a linear combination of other variables v 1 , v 2 , . . . , v n , so that ∃i ∈ {1, . . . , n}, v = v i , and v ′ is live by linearity in p.

Finally, a variable is a dimension in the abstract domain if and only if it is live by linearity and it is not defined as a linear combination of program variables.

A basic block of code therefore amounts to a parallel assignment operation between live-by-linearity variables (v 1 , . . . , v n ) → (f 1 (v 1 , . . . , v n ), , . . . , f n (v 1 , . . . , v n )); such operations are directly supported by APRON. This has three benefits: (i) it limits the number of dimensions in the abstract values, since polyhedra libraries typically perform worse with higher dimensions;5 (ii) the abstract operation for a single path in path-focusing methods also is a (large) parallel assignment; (iii) as suggested by Miné [START_REF] Miné | Symbolic methods to enhance the precision of numerical abstract domains[END_REF], this approach is more precise than running abstract operations for each program line separately: for instance, for y=x; z=x-y; with precondition x ∈ [0, 1], a line-by-line interval analysis obtains y ∈ [0, 1] and z ∈ [-1, 1] while our "en bloc" analysis symbolically simplifies z = xx = 0 and thus z ∈ [0, 0].

In the event that a node is reachable only by a single control-flow edge (which may occur because of dead code, or during the first phases of guided static analysis), the φ operation reduces to a copy of the values flowing from that edge. In this case, our tool just propagates symbolic values through the predecessor node, without introducing φ-variables.

Use

PAGAI takes as input an LLVM bitcode file, and outputs an inductive invariant for each control point in P R (typically, the widening points). When a program contains an assert (...) function call, PAGAI also outputs whether the statement has been proved. It is also possible to add some preconditions about the variables, etc, using a function assume (...) . Both assert and assume are implemented as C macros. assert (x) is roughly defined as if (! x) assert fail (); , and the tool just tests for the reachability of assert fail (); : if it is unreachable, then the assertion is true. assume works with the same principle, and is defined as if (! x) assumption declared(). Both assert fail and assumption declared are noreturn functions, terminating the program immediately.

Current limitations of the tool, possible future works

Our tool currently only operates over scalar variables from the SSA representation and thus cannot directly cope with arrays or memory accessed through pointers. We therefore run it after the "memory to registers" (mem2reg) optimization phase in LLVM, which lifts most memory accesses to scalar variables. The remaining memory reads are treated as nondeterministic choices, and writes are ignored. This is a sound abstraction. 6 The analysis is currently intraprocedural: function calls are ignored in a sound way (the return value is a nondeterministic choice, the value of all variables escaping from the local scope is discarded...). In order to increase precision, we apply function inlining as an LLVM optimization phase. Plans for interprocedural analysis include computing input/output summaries for functions as elements of the abstract domain (e.g. if the function operates over variables x and y, then one could compute a polyhedron over (x, y, x ′ , y ′ ) encompassing all input-output pairs) or as more general formulas.

Since it is often advantageous to distinguish whether a loop has been executed at least once, 7 we unroll every loop once, again with a LLVM optimization phase.

Our tool currently assumes that integer variables are unbounded mathematical integers (Z) and floating-point variables are real (or rational) numbers. Techniques for sound analysis of bounded integers, including with wraparound, and of floating-point operations have been developed in e.g. the Astrée system [START_REF] Blanchet | A static analyzer for large safety-critical software[END_REF][START_REF] Cousot | The ASTR ÉE analyzer[END_REF], but porting these techniques to our iteration schemes using SMT-solving requires supplemental work. It is unclear whether one should use bitvector arithmetic inside the SMT formula, or use mathematical integers with explicit splits for wraparound. 8 Our implementation of path-focusing currently does not use true acceleration techniques, as proposed by Monniaux et Gonnord [START_REF] Monniaux | Using bounded model checking to focus fixpoint iterations[END_REF]. Instead, it simply runs widening and narrowing iterations on a single path.

We currently analyze each strongly connected component of the control-flow graph in topological order; thus each loop nest gets analyzed as a single fixed point. An alternative method would be to recursively decompose the strongly connected components (for structured programs, this amounts to reconstructing the nested loop structure) and summarize the inner loops before analyzing the outer loop.

The analysis is currently only forward, even though nothing in the techniques implemented is specific to forward analysis. A possible extension would therefore be backward analysis from the assert fail () statements. 6 As rightly pointed out by a referee, this is a sound abstraction only if memory safety is assumed. The mem2reg preprocessing phase also assumes memory safety, as well as, possibly, the absence of other undefined behaviors as defined by the C standard. This is the price of using the front-end from a generic compiler: C compilers have the right to assume that undefined behaviors do not occur, including in preprocessing and optimization phases. 7 Consider the very simple loop for( int i=0; i<n; i++) . The obvious loop invariant is 0 ≤ i ≤ n, but it is valid only if n > 0. One would thus need to use disjunctive loop invariants to obtain 0 ≤ i ≤ n ∨ (i = 0 ∧ n ≤ 0). It is much simpler to unroll the loop once.

8 E.g. an operation z = x + y over n-bit signed integers would appear as the disjunction of three statements z (resp. ) gives the percentage of invariants stronger (more precise; smaller with respect to inclusion) with the left-side (resp. right-side) technique, and "uncomparable" gives the percentage of invariants that are uncomparable, i.e neither greater nor smaller; the code points where both invariants are equal make up the remaining percentage

= x + y ∧ -2 n-1 ≤ x + y < 2 n-1 , z = x + y + 2 n ∧ -x + y < -2 n-1 , z = x + y -2 n ∧ x + y ≥ 2 n

Experiments

We conducted extensive experiments on real-life programs in order to compare the different techniques, mostly on open-source projects (Tab. 1) written in C, C++ and Fortran.

Precision of the various techniques

For each program and each pair (T 1 , T 2 ) of analysis techniques, we list the proportion of control points in P R where T 1 (resp. T 2 ) gives a strictly stronger invariant, denoted by (resp. ), and the proportion of control points where the invariants given by T 1 and T 2 are uncomparable for the inclusion ordering (the remainder of the control points are thus those for which both techniques give the same invariant). We use convex polyhedra as the abstract domain.

Let us briefly comment the results given in more details in Table 2. Guided Static Analysis from Gopan et Reps [START_REF] Gopan | Guided static analysis[END_REF] improves the result of the classical Abstract Interpretation in 2.21% of the control points in P R . Path-focusing from Monniaux et Gonnord [START_REF] Monniaux | Using bounded model checking to focus fixpoint iterations[END_REF] finds better invariants in 4.13% of the control points.

However, these two techniques also lose precision in an important number (4.64% for G, 5.14% for PF) of control points, and obtain worse results than the classical many times. This result is unexpected, and could be partially explained by bad behaviour of the widening operator.

Finally, our combined technique gives the most promising results, since it is statistically more precise than the other techniques. It improves the precision of the inductive invariant in 8.29% to 9.86% of the control points compared to The analysis using disjunctive invariants greatly improves the precision of the analysis (for 14.46% of the control points in P R compared to G+PF), at the expense of a higher time cost (see Table 3). It also gives worse results in 6.85% of the points, most probably because of a non-optimal choice of the σ function, detailed in [START_REF] Henry | Succinct representations for abstract interpretation[END_REF].

While experimenting with techniques that use SMT-solving, we encountered some limitations due to non-linear arithmetic in the analyzed programs. Indeed, the SMT-solver is not able to decide the satisfiability of some SMT-formulae expressing the semantics of non-linear programs. In this case, we skipped the functions for which the SMT-solver returned the "unknown" result. This limitation occurred very rarely in our experiments, except for the analysis of Lapack/Blas, where 798 over the 1602 functions have been skipped. Lapack/Blas implements matrix computations, which use floating-point multiplications. In cases where the formula is expressed in too rich a logic for the SMT-solver to deal with, a number of workarounds are possible, including: (i) Linearization, as per Miné [START_REF] Miné | Symbolic methods to enhance the precision of numerical abstract domains[END_REF], which overapproximates nonlinear semantics by linear semantics. (ii) Replacing the results of nonlinear operations by "unknown". Neither is currently implemented in our tool. Table 3 gives the execution time of the different analysis techniques. It is interesting to see that Path-focusing is sometimes faster than the classical algorithm. This seems due to the fact that this algorithm computes inductive invariant on a small number of control points compared to classical approaches, thus leading to fewer operations over abstract values.

Precision of Abstract Domains

For each program and each pair (D 1 , D 2 ) of abstract domains, we compare by inclusion the invariants of the different control points in P R = P W (Tab. 4). Statistically, the domain of convex polyhedra gives the better results, but commonly yields weaker invariants than the domains of octagons/intervals; this is a known weakness of its widening operator [START_REF] Monniaux | Stratified static analysis based on variable dependencies[END_REF]. The Octagon domain appears to be much better than intervals; this is unsurprising since in most programs and libraries, bounds on loop indices are non constant: they depend on some parameters (array sizes etc.).

The Lapack/Blas benchmarks are unusual compared to the other programs. These libraries perform matrix computations, using nested loops over indices; such programs are the prime target for polyhedral loop optimization techniques and it is therefore unsurprising that polyhedra and octagons perform very well over them.

The analysis of linear equalities (PKEQ) performs very fast compared to other abstract domains, but yields very imprecise invariants: it only detects relations of the form i a i x i = C where a i and C are constants.

Using the reduced product of convex prolyhedra with linear congruences (PKGRID) improves the analysis by 2.52%.

Finally, we evaluated the benefits of the improved version of the widening operator for convex polyhedra from Bagnara et al. [START_REF] Bagnara | Precise widening operators for convex polyhedra[END_REF], compared to the classical widening. We found that the improved version from Bagnara et al. [START_REF] Bagnara | Precise widening operators for convex polyhedra[END_REF] yields more precise invariants for 3.70% of the control points in P R .

Future Work

It is not totally relevant to compare by inclusion the abstract values obtained by the various analysis techniques. Indeed, a slightly smaller invariant may not always be useful to prove the desired properties. Future work should thus include experiments with better comparison metrics, such as (i) the number of assert that have been proved in the code. Unfortunately, it is difficult to find good benchmarks or real life programs with many assert statements; (ii) the number of false alarms in a client analysis that detects array bound violations, arithmetic overflows, etc.

Figure 1 :

 1 Figure 1: Example of program, where the loop behaviour vary depending on a variable phase.

Table 1 :

 1 List of analyzed open-source projects, with their respective number of lines of code, and their number of control points in P R

	Name	kLOC	|PR|
	a2ps	55	2012
	gawk	59	902
	gnuchess	38	1222
	gnugo	83	2801
	grep	35	820
	gzip	27	494
	lapack/blas	954 16422
	make	34	993
	tar	73	1712

  -1 : one "normal" control path and two "overflow" paths.

	Benchmark		G/S		PF/S	PF/G	G+PF/PF	G+PF/G	DIS/G+PF
				unc.	unc.	unc.		unc.	unc.	unc.
	a2ps-4.14	0.28 0	0	4.82 2.55 2.27 4.54 2.55 2.27 6.81 0.28 0	8.23 0	0	13.06 3.40 0.56
	gawk-4.0.0	4.62 0	0	3.70 20.37 0.92 0.92 22.22 0	22.22 0	0	11.11 2.77 0	16.66 2.77 0.92
	gnuchess-6.0.0 1.51 3.47 0	6.50 4.33 0	6.72 3.25 0.21 6.72 2.38 0	10.19 2.38 0	15.18 2.81 3.03
	gnugo-3.8	0.51 4.44 0.34 11.45 4.27 3.07 12.13 4.27 2.73 10.25 3.07 2.05 17.77 3.76 0.34 9.05 11.28 4.78
	grep-2.9	0	6.19 0.47 1.90 4.76 0.47 3.80 1.90 1.90 7.61 2.38 0	8.57 2.38 0	10.47 5.23 0.47
	gzip-1.4	0.58 7.01 1.75 1.75 12.86 1.16 3.50 8.18 1.16 15.78 2.92 1.16 17.54 1.75 0	17.54 15.78 1.16
	lapack-3.3.1	2.60 5.77 0.40 3.11 5.06 1.03 4.66 3.47 1.62 7.55 1.06 0	9.24 1.06 0.81 16.11 7.09 1.34
	make-3.82	2.61 0.52 0	1.82 6.26 1.82 1.56 8.09 1.82 11.74 0.52 0	6.52 2.34 1.56 12.27 4.43 0.78
	tar-1.26	4.53 3.27 0	5.28 2.77 0	2.77 2.01 0.75 7.05 0.50 0	7.05 0.25 0	9.82 7.05 1.51

Table 2 :

 2 Results of the comparison of the various techniques described in this paper: classic Abstract Interpretation (S), Guided Static Analysis (G), Pathfocusing (PF), our combined technique (G+PF), and its version using disjunctive invariants (DIS). For instance, G/S compares the benefits of Guided Static Analysis over the classic Abstract interpretation algorithm.

Table 3 :

 3 Execution time for each technique, expressed in seconds the three previous techniques. Still, we obtain worse result in a non-negligible number of cases (2.02%).

Table 4 :

 4 Results of the comparison of the various abstract domains, when using the same technique (G+PF). We used as abstract domains Convex Polyhedra (PK and POLY), Octagons (OCT), intervals (BOX), linear equalities (PKEQ) and the reduced product of NewPolka convex polyhedra with linear congruences from the Parma Polyhedra Library[START_REF] Bagnara | The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems[END_REF]. (PKGRID). The last column compares the domain of Convex Polyhedra with the improved widening operator from Bagnara et al.[START_REF] Bagnara | Precise widening operators for convex polyhedra[END_REF] (POLY*), and Convex Polyhedra using the classical widening operator (POLY). POLY and POLY* use the PPL[START_REF] Bagnara | The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems[END_REF]. , and "unc." are defined as in Tab. 2.

A preliminary analysis pass selects a subset of nodes that cuts all cycles in the control-flow graph, by selecting all targets of return edges in a depth-first search traversal; when applied to a structured program, it selects loop headers.

Certain abstract domains express relationships, such as linear congruences, that certain decision procedures cannot deal with. It is at present necessary that the decision procedure reflects semantics at least as precise as those of the abstract domain. This limitation will be lifted in the future.

It is unfortunately impossible to ignore differences between solvers behind the supposedly standard interface, since different solvers may support slightly different sets of operators and settings and may return models in different formats.

It would be possible to obtain a feedback vertex set minimal with respect to inclusion by successive removal of nodes. Obtaining one of minimal cardinality is an NP-complete

The additional dimensions express linear equalities between variables, which are directly handled by polyhedra library. They should therefore cost little assuming some sparse representation of the constraints. Alas, several libraries, including APRON, compute with dense vectors and matrices, which means that any increase in dimensions slows computations.


V D'auria

O Morin

C Fabre

J Laurat

Effect of the heralding detector properties on the conditional generation of single-photon states

Single-photons play an important role in emerging quantum technologies and information processing. An efficient generation technique consists in preparing such states via a conditional measurement on photon-number correlated beams: the detection of a single-photon on one of the beam can herald the generation of a single-photon state on the other one. Such scheme strongly depends on the heralding detector properties, such as its quantum efficiency, noise or photon-number resolution ability. These parameters affect the preparation rate and the fidelity of the generated state. After reviewing the theoretical description of optical detectors and conditional measurements, and how both are here connected, we evaluate the effects of these properties and compare two kind of devices, a conventional on/off detector and a two-channel detector with photon-number resolution ability.

I. INTRODUCTION

A driving component for the development of diverse quantum information applications is the ability to efficiently engineer non-classical states of light [1]. In particular, a great number of communication or computing protocols require single-photon states [2]. The control of single quantum objects provides a way to generate such states [3]. Another procedure, probabilistic but heralded, consists in measuring one mode of an entangled state, which results in projecting the other mode according to the measurement result: in the ideal case of twin beams, the detection of a single-photon in one beam projects the other one into a single-photon state [4]. The physical realization of this scheme critically relies on the performances of the twin-photon generator but also of the single-photon detector used to herald the preparation.

Indeed, realistic detectors do not perfectly resolve photon numbers, have limited quantum efficiency and can be noisy [5]. These properties directly translate into the fidelity of the generated state and its preparation rate. The goal of this paper is to evaluate how these properties impact the conditional preparation of single-photon states. We will consider the typical case of twin beams produced by two-mode spontaneous parametric down conversion. To illustrate the effect of the heralding detector properties, we will analyze two different detectors, a conventional APD and a single-loop time-multiplexed detector. The present work provides a detailed analysis of the experimental characterization of these detectors [6] and of the modeling of the single-photon state preparation using such detectors.

The paper is organized as follows. In section II, we first recall the general description of optical detectors by positive operator valued measure (POVM) and describe the conditional measurement scheme based on entangled beams. Given the detector POVM, we derive the general expression of the generated state. We illustrate this section by considering two specific detectors. Section III is then devoted to the experimental characterization of such detectors via quantum detector tomography. In Section IV, by numerically simulating the entanglement resource, we predict the properties of the generated state that would be obtained if such detectors are used. We compare the two devices. We finally discuss the dependence of the generated state in the general case obtained by using the theoretical expressions of the POVM elements. This study enables us to determine the fidelity and preparation rate for the two heralding detectors, as a function of the noise background, quantum efficiency and entanglement resource.

II. THEORETICAL DESCRIPTION OF SINGLE-PHOTON DETECTORS AND QUANTUM STATE ENGINEERING

Quantum state engineering is an interplay between the entangled resource and the measurement performed by the heralding detector. In this section, we remind how the detector properties can be described in the most general case by a positive-operator valued measure and we provide the general expression of the state prepared by a measurement performed on one beam of the two correlated ones generated by spontaneous parametric dowconversion. Two particular detectors are considered.

A. Description of a detector by a POVM

A detector can be fully described by its positive operator valued measure [START_REF] Helstrom | Quantum detection and estimation theory[END_REF], i.e. by a set of semipositive hermitian { Πn } associated to each of its N possible outcomes labeled by integer "n". These operators sum up to the identity, N -1 n=0 Πn = 1. They enable to make predictions on the measurement outcomes. For any impinging states ρ on the detector, the probability p n (ρ) of obtaining the outcome "n" is given by:

p n (ρ) = Tr[ρ Πn ] (1)
where Tr stands for the trace.

In the following, we will consider the case of photon counters, which are phase-insensitive. In this specific case, the outcomes "n" correspond to "n clicks". For ideal detectors with perfect photon number resolution ability, the number of clicks directly gives the number of impinging photons. Therefore, the corresponding POVM is the set of projectors on the photon-number states: Πn = |n n|.

However, realistic detectors are affected by non-unit quantum efficiency, imperfect counting ability and intrinsic noise. The general expression for Πn can then be written as a sum of projectors:

Πn = ∞ k=0 r k,n |k k|. (2)
Let us note that the coefficient r k,n can be read as:

r k,n = Tr[ Πn |k k|] = P (n|k). (3)
It thus corresponds to the conditional probability P (n|k) to obtain the outcome "n" giving an impinging Fock state |k . This expression is very convenient to determine the POVM coefficients of a given detector implementation.

B. General expression of the POVM for two experimental cases

We will consider here the case of two single-photon counters: a conventional on/off avalanche photodiode (APD) and a home-made single-loop time-multiplexed detector (TMD). We give the expression of the POVM elements in the general case, including non-unit quantum efficiency η and dark noise with Poissonian statistics, which corresponds to many practical situations.

Including non-unit quantum efficiency

A conventional APD has a limited counting ability as it provides a binary outcome: it is only able to tell whether photons (whatever their number) have been detected (on, one click) or not (off , no click). In the ideal case, the two corresponding POVM elements are given by Πoff = |0 0| and Πon = 1 -|0 0|. In the case of non-unit quantum efficiency η, the POVM for the APD detector can be written as [START_REF] Ferraro | [END_REF]:

   Πoff (η) = ∞ k=0 r k,off (η)|k k| = ∞ k=0 (1 -η) k |k k| Πon (η) = ∞ k=0 r k,on (η)|k k| = 1 -Πoff (η, ν). (4)
As stated by equation (3), the coefficient r k,off is given by the expectation value of the operator Πoff for an impinging Fock state |k . In the absence of noise, this value is equal to the probability of not detecting k photons for a quantum efficiency η: it is indeed equal to the probability to not detect a photon, 1 -η, to the power of k.

The second detector we consider is a single-loop time-multiplexed detector with photon-number resolution ability (Fig. 1c). Indeed, it is able to provide an additional information by distributing the light to be detected in two temporal bins. The incoming photons are sent to a beamsplitter (reflectivity R in intensity) whose outputs are delayed by a time interval ∆T and recombined before being detected by an APD [START_REF] Achilles | [END_REF]. If two photons impinge on the detector, they are split toward different paths with probability 2R(1 -R) and, in this case, they are detected by the APD as two subsequent events. Three outcomes are thus possible: no click, 1 click and 2 clicks. For a given quantum efficiency η of the APD used for the detection of the two bins, the POVM elements of the TMD take the general form:

           Π0 (η) = ∞ k=0 r k,0 (η)|k k| Π1 (η) = ∞ k=0 r k,1 (η)|k k| Π2 (η) = 1 -Π0 (η) -Π1 (η). (5)
The POVM coefficients are calculated following the definition given in (3):

r k,0 (η) = P (0|k) = p k=0 R p (1 -R) k-p k p r k-p,off r p,off = (1 -η) k (6)
and

r k,1 (η) = P (1|k) = p k=0 R p (1 -R) k-p k p (7)
×(r k-p,on r p,off + r p,on r k-p,off ) = (1 -η) k p k=0 R p (1 -R) k-p k p ×(-2 + (1 -η) p-k + (1 -η) -p ) = (1 -η) k -2 + 1 + Rη 1 -η k + 1 + T η 1 -η k .

Including dark noise

We now include the effect of Poissonian dark counts in the description. We note ν the mean number of dark counts in the detection window, which is defined before the 'black-box' detector: e -ν is thus the probability of no dark counts whatever the specific detector implementation. For instance for the TMD, where the mode is split into two temporal bins, e -ν/2 is the probability of no dark counts into each bin and (e -ν/2 ) 2 = e -ν for the two bins.

The general expression of the POVM in the presence of noise can be written as a function of the POVM without noise. Using (3), one obtain for the APD

r k,off (η, ν) = e -ν r k,off (η) r k,on (η, ν) = 1 -e -ν r k,off (η) (8)
while for the TMD it can be read as:

r k,0 (η, ν) = e -ν r k,0 (η) r k,1 (η, ν) = e -ν/2 r k,1 (η) + 2(e -ν/2 -e -ν )r k,0 (η). (9)

C. Conditional state preparation with twin beams

We now detail the conditional preparation. As explained before, a general strategy for the conditional preparation of quantum states relies on the use of entanglement: due to quantum correlations, measuring one mode of an entangled state results in projecting the other mode according to the result of this measurement. By denoting ρAB the two-mode state, a measurement performed on mode B characterized by the POVM Πn leads to the preparation on mode A of the conditional state ρc , which can be written as:

ρc = 1 P r(n) Tr B ρAB 1A ⊗ Πn (10)
where Tr B stands for the partial trace over mode B and 1A is the identity operator acting on mode A. P r(n) is the probability to obtain the outcome "n" on mode B and is thus proportional to the preparation rate. It can be read as:

P r(n) = Tr AB ρAB 1A ⊗ Πn . (11)
In this paper, we consider as an entangled state resource the twin beams produced by perfect two-mode spontaneous parametric down-conversion (SPDC):

|Ψ AB = 1 -|λ| 2 ∞ k=0 λ k |k A |k B ( 12
)
where the squeezing parameter λ, which varies between 0 and 1, is related to the intensity gain in the downconversion process. This parameter determines the average photon number per mode as N = |λ| 2 /(1 -|λ| 2 ).

From the previous general expressions (10) and (11), it follows that the conditional state ρc is given by ρc

= ∞ k=0 |λ| 2k r k,n |k k| ∞ k=0 |λ| 2k r k,n (13)
where r k,n are the coefficients of the POVM element Πn . The probability P r(n) can also be written as a function of the squeezing parameter and POVM coefficients as

P r(n) = (1 -|λ| 2 ) ∞ k=0 |λ| 2k r k,n . (14)
For an ideal photon-number resolving detector, r k,n (η, ν) = δ k,n , the conditional state resulting from a heralding measurement Πn = |n n| reduces thus to a Fock state |n for any values of λ as expected. Only the preparation rate varies with this parameter. In the more general case, ρc tends to the normalized POVM element in the limit of high gain:

ρc λ→1 -→ Πn Tr Πn . ( 15
)
Note that defining the non-classical character of a quantum measurement is not straightforward as the POVM elements are not normalized and thus do not correspond to a quantum state. However, conditional preparation provides a good insight into this subtle question. Given equation ( 15), the non-classical properties of a detector can be seen as the non-classical properties of the state generated by a conditional measurement in the limit of high gain. Significantly, this expression also corresponds to the expression of the state retrodicted from the measurement outcome [10][11][12]. This state enables to make predictions (called retrodictions) about state preparation leading to this result. The non-classical properties of the detector can then be associated in this approach with the properties of the retrodicted state [12].

III. QUANTUM DETECTOR TOMOGRAPHY AND EXPERIMENTAL DETERMINATION OF THE POVM

We now turn to the experimental characterization of detectors. The complete characterization of a detector requires, for each of its POVM elements Πn , the knowledge of all the coefficients {r k,n (η, ν)}. This knowledge can be obtained experimentally by performing the socalled quantum detector tomography (QDT) [6,[13][14][15][16][17][18][19]. We present here the experimental setup for QDT and the results for the two detectors we are focusing on in the present study.

A. Procedure and setup

The procedure for QDT consists in probing the detector by sending a tomographically complete set of known states { ρj } and in recording the number of times (f n,j ) each outcome "n" occurred in the measurement for each probe state. By using equation (1), a maximum likelihood algorithm (ML) allows for reconstructing the POVM elements { Πn } by searching for the set of the r k,n (η, ν) coefficients that provide the optimal matching between the measured f n,j and the theoretical p n,j . Significantly, the ML does not require any a priori assumptions on the detector under investigation. The details of the procedure can be found in [14].

In our experiment, we used as probe states a set of coherent states |α j α j | of different amplitudes, generated by strongly attenuating the light coming from a pulsed laser source. The experimental setup is shown in Figure 1. Light pulses at 795 nm are provided by a femtosecond laser source (MIRA900) with a repetition rate set to 1.187 MHz thanks to a pulse picker device (9200 Coherent). In order to tune the average photon number per pulse, |α j | 2 , the laser beam is sent through a variable attenuation device consisting of a half wave plate (λ/2) and a polarizing beam splitter (P BS). The power of the output beam is controlled by tapping a known fraction toward a power meter. A set of well calibrated optical densities (total O.D.≈7 ) supplies the attenuation necessary to reach the regime of few photons per pulse: |α j | 2 can be indeed adjusted from 0 to 100 by steps of 0.1. The probe beam is sent to the "black-box" containing the unknown detector through an optical fiber. The losses due to the coupling are taken into account when estimating the average photon number. The error on the average photon number is of the order of 5%, mostly due to the residual laser intensity fluctuations between subsequent pulses.

B. Experimental reconstruction in the absence of noise

We performed the detector tomography procedure on the two different devices presented in section II: a standard on/off avalanche photodiode (APD) and a single-loop time-multiplexed detector (TMD). The APD (Perkin Elmer SPCM-AQR-13) is sketched on figure 1b while the multiplexed detector is shown in figure 1c. For the TMD, the light is split toward two channels: pulses going to the upper channel undergo a delay of ∆T = 150 ns with respect to those in the other channel. The two paths are eventually spatially recombined using orthogonal polarizations (this recombination avoids extra 50% losses) and sent to an APD. As ∆T is larger than the detector dead time, the arrival of two photons will correspond to two subsequent events. This setup leads to three possible responses: off, 1 click or 2 clicks. For both detectors, the overall quantum efficiency has been set to 0.28 ± 0.02.

Figure 2 gives the experimental results of the QDT performed on both detectors (first line for the APD, second line for the TMD). Column (a) provides the frequency of the different outcomes as a function of the average photon number |α| 2 . Column (b) then gives the reconstructed operator, Πon for the APD and Π1 for the TMD, and column (c) finally shows the corresponding Wigner functions. As it can be seen, both are negative at the origin, which is a strong signature of the non-classicality of the detectors. Let us underline that this detector negativity is a critical property for quantum state engineering. Indeed, the preparation of a quantum state with nega-

C. Experimental reconstruction in the presence of noise

We performed similar QDT by adding noise to the detection process. The background noise is controlled by injecting on the detector, together with the probe states required for the QDT, a continuous-wave coherent beam at 1064 nm (Diabolo, Innolight). By adjusting the laser power, we are able to mimic different dark count levels with Poissonian statistics. As in section II, we note ν the mean number of dark counts in the detection window. Figure 3 gives the Wigner functions for the two devices and for different noise levels. As it can be seen, the negativity decreases with the noise, and eventually disappears. This gradual disappearance of the negativity witnesses in a quantitative way the degradation of the detector performances.

IV. SINGLE-PHOTON GENERATION WITH APD AND TMD

We now turn to the conditional generation of singlephoton states using these two specific detectors. By simulating the entanglement resource, we first examine the state one would obtain using the characterized detectors. We then consider the more general case given by the theoretical POVM coefficients derived in section II, in particular for high quantum efficiency. This section illustrates the difference between the two detectors and the conditions in which the photon-number resolution ability of

-3 -2 -1 0 1 2 3 v = 0.00 v = 0.03 v = 0.08 v = 0.16 (b) (c) x
FIG. 4: Effect of the dark counts on the conditional state generation. The state is calculated from Eq.13 by using the experimentally reconstructed POVM coefficients for the APD and for the TMD. Figure (a) gives the fidelity between a single-photon state and the state generated using the APD (dashed) or the TMD (straight), as a function of λ and for different dark count levels. Figures (b) and (c) represent the cross-section of the Wigner functions of a single-photon state (green), of the states generated using an APD (red) and using the TMD (blue), in the absence of noise (ν = 0) and respectively for λ = 0.1 and λ = 0.7

the two-channel TMD is useful.

A. Fidelity of the state generated with the characterized APD and TMD

Given the reconstructed POVM elements for the APD and the TMD, expression (13) enables us to determine the state one would conditionally generate by using these detectors and correlated photon pairs generated by SPDC. The fidelity of the generated state with the target one (pure state) can then be calculated as the overlap of the Wigner function, W c (x, y) associated to ρc and the Wigner function of the target state W t (x, y) [20,21]:

F = +∞ -∞ W c (x, y)W t (x, y)dxdy +∞ -∞ |W t | 2 (x, y)dxdy (16)
In the following we calculate the fidelity with a singlephoton state, whose Wigner function can be written as W t (x, y) = 2 π e -2(x 2 +y 2 ) [-1 + 4(x 2 + y 2 )]. Figure 4a gives the fidelity of the generated state for the APD and the TMD as a function of the squeezing parameter λ. We recall that increasing λ leads to a higher number of photons in the twin modes. Therefore, in the limit of λ → 1, the fidelity goes to 0 due to multi-photon pairs, which can not be resolved by the present detectors. Very low squeezing parameter is usually required to overcome their limited photon-number resolution. In this case, the two detectors behaves similarly. Figures 4b and4c provide the cross-sections of the Wigner functions in the absence of noise and for two different values, λ = 0.1 and λ = 0.7. In both cases, the generated states are very close. In the first case, however, the fidelity with a single-photon state is high while it strongly decreased for higher values. FIG. 5: Fidelity event rate in the absence of noise (ν=0) and for a quantum efficiency η=0.9. Plot (a) gives the fidelity a single-photon state and the state generated using the APD (red) or the TMD (blue) as a function of the squeezing parameter λ. Plot (b) shows the event rate R as a function of the targeted fidelity (λ is chosen accordingly).

In all the configurations, the TMD enables to reach a slightly larger fidelity due its photon-number resolution ability (yet limited). This gain appears for increasing value of λ, while it is expected to disappear for vanishing λ due to the the low-photon number occupancy of the modes. As it can be seen, the difference between the results one would obtain using the APD and a single-loop TMD is however small. This is due to the low quantum efficiency of the avalanche photodiode used here. In the following, we present the general case, without being limited by the efficiency η and noise ν imposed by a specific experimental implementation.

B. General case

By using the theoretical expressions for the POVM coefficients as given in section 2, we can predict the modification of the conditional states and of their generation probability (the rate of heralded events) as functions of the detector parameters.

In an ideal measurement, involving a projective detector the result 1-click of a measurement performed on mode B heralds the generation of a single-photon state in mode A (F =1) , whatever the statistics of the initial twin beams, i.e. for all values of λ. In this case, the squeezing parameter λ only affects the probability of generating the state, R ideal = (1 -|λ| 2 )|λ| 2 . For realistic detectors, the detector parameters affect both the generated state and the event rate. We compute here the fidelity of the generated state with a single-photon state, by making use of the expressions of r k,on and r k,1 of equations [START_REF] Ferraro | [END_REF][START_REF] Achilles | [END_REF]. For the APD, the fidelity F on can be written as

F on = λ 2 • (1 -e -ν (1 -η)) 1 1-λ 2 - e -ν 1-(1-η)λ 2 (17)
and the rate of events R on is given by: Similarly, for the state heralded by the TMD, we obtain a fidelity

R on = 1 - e -ν (1 -λ 2 ) 1 -(1 -η)λ 2 . ( 18
)
F 1 = λ 2 • (1 -η/2 -e -ν/2 (1 -η)) 1 1-(1-η/2)λ 2 -e -ν/2 1-(1-η)λ 2 (19)
with a corresponding event rate R 1 :

R 1 = 2(1 -λ 2 ) -e -ν 1 -(1 -η)λ 2 + -e -ν/2 1 -(1 -η/2)λ 2 . (20)
As an example, we consider the case of a high quantum efficiency (η = 0.9). In the absence of noise (ν = 0), figure 5 gives the fidelity and preparation rate as a function of the squeezing parameter. As already seen in the previous section, the fidelity is decreasing with increasing λ due to the multi-photon pairs emitted in the SPDC process. While the difference between the two detectors was small for a low quantum efficiency, it can be clearly seen now. The photon-number resolution ability of the TMD, yet limited, enables us to reach a larger fidelity for all values of λ. Similarly, for a targeted fidelity, the TMD also provides a higher count rate, as shown in figure 5b, as a higher λ can be used.

We finally compare the two detectors in the presence of noise. Figure 6 shows the fidelity as a function of λ and ν, still for a quantum efficiency η = 0.9. For a given value of noise, the TMD enables to reach a better fidelity. As the noise increases, the difference between the two detectors decreases. As it been underlined previously, for a given noise level, there exists an optimal value of λ for the fidelity. For the squeezing parameter going to zero, the fidelity drops as the signal to noise ratio decreases, i.e. the noise results in a large rate of false heralded events relative to the low signal.

V. CONCLUSION

Beyond its fundamental significance, the study of optical detectors has become in the last years more and more crucial for quantum information, in particular in the context of quantum state engineering and measurement-driven processes. We have presented here the general framework for conditional state preparation, which is an interplay between the resource and the heralding detector. In particular, we have taken the example of the conditional preparation of single-photon states and compared two detectors that can be used for such a preparation, an avalanche photodiode and a single-loop time-multiplexed detector. Four parameters are important in such a scheme: the entanglement resource defined here by the squeezing parameter λ, i.e. the photon-number occupancy of the correlated modes, the photon-number resolution ability of the detector, i.e. its capability to discriminate multi-photon events, the noise of the detector and its quantum efficiency. We investigated the heralded state one would obtain given different sets of these parameters. For low quantum efficiency, as we shown experimentally, the TMD only provides a small gain in the heralding process. However, the effect of the photon-number resolution ability of the TMD clearly appears for larger quantum efficiency, enabling in particular a higher preparation rate for a given fidelity of the generated state.

FIG. 1 :

 1 FIG. 1: Experimental quantum detector tomography. (a) The detector, shown here as a black-box, is probed with coherent pulses coupled into a single-mode fiber. A fraction of the light is tapped and measured with a calibrated power-meter to adjust the amplitude of the probe. Two detectors are characterized: (b) a single-photon counting module (APD) and (c) a two-channel time-multiplexed detector.

2 FIG. 2 : 16 FIG. 3 :

 22163 FIG. 2: Experimental data and reconstruction of the POVM elements. The first line corresponds to the APD while the second line gives the results for the TMD. Column (a) gives the bare tomographic data, i.e. the probability of the different outcomes as a function of the average photon number of the coherent probe pulses. Column (b) shows the reconstructed POVM Πon for the APD and Π1 for the TMD. Finally, Column (c) provides the Wigner representation of these operators.

FidelityFIG. 6 :

 6 FIG.6: Fidelity in the presence of noise and for a quantum efficiency η=0.9. Plot (a) gives the fidelity between a singlephoton state and the state generated using the APD (red) or the TMD (blue) as a function of the squeezing parameter λ and noise ν. Plot (b) represents the fidelity as a function of λ for a noise ν=0.08.

This work was supported by the BQR from Université Pierre et Marie Curie and the CHIST-ERA ERA-Net under the QScale project. V. D'Auria acknowledges the financial support from the European Commission under the Marie Curie Program. Claude Fabre and Julien Laurat are members of the Institut Universitaire de France.