Anne-Marie Vercoustre
email: anne-marie.vercoustre@inria.fr

François Paradis
email: francois.paradis@cmis.csiro.au

Metadata for Photographs: from Digital Library to Multimedia Application

This paper describes the production of an educational multimedia CD-ROM about French rural houses and farms, and how to renovate them without losing their traditional features. The educational message is illustrated with many photographs of non-renovated or renovated houses, and made explicit through comments and descriptions associated with the photos. The paper focuses on the XML metadata describing the photos and the use of this metadata for the automatic generation of Web pages. We first report on the usability of the Dublin Core for interoperable photographs metadata, together with more detailed XML descriptions to support a specific multimedia application. We then show how to generate the Web pages by defining HTML document prescriptions which embed queries to the XML metadata, using Norfolk, a virtual document generator. The approach can be used in various applications ranging from personal virtual photo albums to complex virtual museum.

Introduction

Digital Libraries provide access to an increasing variety of digital multimedia information, including images, photos, sound and video. For many years Libraries and Digital Libraries have been relying on classification and indexing schemas for supporting retrieval of bibliographic references and documents, while Web search engines use a mix of full text indexing and classification. Searching for non textual material like photos, video and sounds 1 requires indexing through related textual descriptions, or metadata, generally in an external document, but possibly encoded within multimedia formats such as JPEG. Metadata, or information about data, have motivated a lot of international interest and effort in the last three years, through the Dublin Core Workshop series [DC], or the Resource Description Framework (RDF) defined by the W3C.

The Dublin Core has attracted the attention of formal resource description communities such as museums, libraries, government agencies, and commercial organisations, as illustrated by the many projects listed on the DC site. However there is very little report on the use of DC metadata for photographs. Before the availability of digital photographs, some effort has been spent on cataloguing photographs although they are not very specific cataloguing tools for photographic material (AAT Art and Architecture Thesaurus, LC thesaurus for Graphic Material), nor appropriate standards. As speculated in [START_REF] James | Cataloguing Photographs in Archival Repositories[END_REF], archivists for photos and graphic collections may have considered their collections as unique and assumed that no imposed standard could work on their collection. This advocates once more for an infrastructure such as RDF that supports the coexistence of complementary, independently maintained metadata packages.

Metadata have been primarily designed to support the retrieval and display of resources. Digital Libraries of the future will not just display raw material stored in their databases, nor will they deliver it in a one-for-all presentation. As claimed in [START_REF] Paepcke | Digital Libraries: Searching Is Not Enough[END_REF], "Searching is not enough". Information will be accessed through user queries, browsing, guided tours, temporal exhibitions, educational courses, etc. The same resource will be used in different contexts, associated with other relevant material. Photographs, for example, will be pulled out with other documents which are associated with them either statically or dynamically. All this information needs to be ready for use during frequent context shifts. The material collected for a particular task needs to be pulled together and kept for near or longterm use in new information artefacts. Users as well as librarians and curators need facilities to construct information compounds or to build flexible presentations of Digital Libraries resources. This paper presents an example of a simple, yet significant, multimedia application (ultimately a CD-ROM) that is automatically generated from XML Dublin Core metadata describing photos. The DC Description element has been enriched with a specific schema to support the target application. A more complex application may require to separate Dublin Core metadata from other XML descriptions and complex documents, but the principle would be the same: the application is generated from page prescriptions which define the page model and the queries to retrieve the appropriate elements (photos, texts) from the XML metadata. Links to other pages can also be modelled, and result in an hypertext which is coherent and easy to modify. The rest of the paper is organised as follows. First we present our application: a CD-ROM about rural housing. We then discuss two problems associated with the production of this CD-ROM: how to express metadata about photographs using Dublin Core, and how to automate the generation of pages with virtual documents using the Norfolk system. The last section will outline some benefits of the approach and will draw some conclusions and further work.

The application

We set out to produce a CD-ROM on rural habitations in a small area near Paris, France, where renovation and modern housing have been developing rapidly in the last thirty years, endangering the traditional aspect of French villages to be completely ruined. The aim of the CD-ROM is to make people more aware of this rural cultural heritage and to provide guidance for renovating houses while preserving their traditional features. About 300 photographs from the various village had been taken in the area to illustrate and support the discourse. They had been assembled into a photo exhibition which toured in several villages during 1992-1993. Following the success of this exhibition we thought it was worthwhile to make this material available on a more permanent and accessible support such as a CD-ROM. Like the exhibition, the multimedia presentation will use mostly photos for supporting the educative message through illustrative and comparative examples. About 150 photos have already been scanned for use in the multimedia presentation. The main advantage of an hypermedia presentation over a traditional exhibition is that some photos can be reused several times, in different contexts, for illustrating different aspects of rural buildings. For example a photo of a nice and well renovated house could be used as an example for roof, windows or facade renovation, associated with the relevant and focused comment.

The CD-ROM, as a more perennial support, needs to provide also detailed information about the buildings, so that the photos may become part of the village archives. Overall information will include: r factual information (full address, date of the photograph, state of the building, etc.) r comments and description about the main interesting features r comments and appreciation about the quality of the renovation (this is somehow tricky to avoid litigation). r comparisons of the same building over time (when photographs or postcards are available)

The user can navigate the CD-ROM using a Web browser. Figure 1 shows the navigational structure. Navigation can be guided by village/street, theme (roof, windows, etc.), or (not shown in the figure ) by examples of renovation (good ones as well as bad ones, on different aspects) or comparison before and after renovation (when available). The description page for a photograph can depend on its context: for example, the description will be different if the user is looking at "roofs" or "windows". Examples of photos can be seen in Figure 2. The digital photos have been processed by a photo laboratory from the colour negatives and put on a read-only CD-ROM. We thought initially of using the KODAK-CD standard to keep the best definition of the photos as recommended in [START_REF]Electronic Library Image Service for Europe[END_REF]. A KODAK Photo-CD can store a maximum of 660Mb of photos (about 100 photos). As we intend to store at least 150 photos, and ultimately much more, it would have been too costly for the budget of the local association who is producing the final CD-ROM (s). Since the application was intended mostly for public education, working images were sufficient for our purpose. We therefore decided to store digital photos as 24-bit images compressed in JPEG, of dimension of 800x537 pixels. It results in image files of size ranging between 42k and 300k, which would allows us to store millions of images on one photo CD-ROM. From these images we produced thumbnail images (200x 134), also called browsing images in [START_REF]Electronic Library Image Service for Europe[END_REF], by reducing the images by 25%, which results in image files of size between 8 and 35k. If smaller images were necessary for an application (iconic images) there will be produced at display time by setting the attributes in the HTML IMG tags.

Metadata for photographs

Although photographs may be more explicit than a long discourse for an humans, they don't describe themselves in term of content as texts do. For texts, authors use many clues to indicate what they are talking about: titles, abstract, keywords, etc. which may be used for automatic cataloguing.

Searching for photos must rely on manual cataloguing, or relate texts and documents that come with the photos. Creating standard metadata for photographs is difficult since one photo may have very different meanings, depending on the context, of whether it is part of a collection, or even on the purpose of a particular end user. Our collection was very specific, and there was no standard for describing this kind of building. At least the Dublin Core offers a framework for describing digital resources and we wanted to experience how it would work for our photos. Our main motivation for using a standard like Dublin Core was to make our photos reusable for other experiments or applications, by ourselves or by other groups.

For example one could think of creating a CD-ROM by village and compare how a house looks today with how it looked in 1900 by comparison with the many available postcards.

Dublin Core

The Dublin Core metadata set [DC] is intended to promote and develop the metadata elements required to facilitate the discovery of resources (documents and images) in a networked environment such as the Internet and support interoperability amongst heterogeneous metadata systems. Dublin Core metadata set consists of fifteen descriptive elements. Commonly understood semantics for these element is described in the reference description [RFC2413] which has been largely stable since 1996, and known as DC 1.0. Although the first aim of Dublin Core is to offer a minimal set of core elements to achieve interoperability, extensibility has been an important issue since the second DC workshop.

Early experience with Dublin Core deployment has made clear the need to support qualification of elements for some applications. Thus, a Dublin Core element may be expressed without qualification or with qualifiers that refine its semantics. Three qualifiers were defined: sub-elements, language and scheme. A sub-element specifies a facet of a given element. The intent is to narrow the semantics of a field, not to extend it. The dot-encoding convention used for this qualifier reflects this. The language qualifier indicates the language used for the content of the element. Finally a scheme qualifier specifies a context for the interpretation of a given element. Typically this will be a reference to an externallydefined scheme or accepted standard. Dublin Core defines scheme as a qualifier that " provides a processing hint that may be used by an application or a person to make better use of the element that is qualified".

We expressed DC metadata in XML as shown in the example given in the appendix. In the next section we describe in detail our use of Dublin Core and the few qualifiers we added (sub-elements and schemes). Our schemes are XML schemas and values for the corresponding elements are therefore expressed also in XML.

Report on our use of DC

Although our collection of photographs is rather modest in size, our use of DC has given rise to a number of small difficulties which are worth reporting on. As mentioned before, very little report on using DC for images and photographs is available today.

We describe below for every DC element, its use in our application.

Title:

What is the title of a photo is not very well defined. It could be seen as the caption of an image, but it is generally dependant of the context. Think of the kind of legends you may write in your family photo album. It may be very informative, or just humorous. In our case we put a very general description that may be used in various contexts, and of some use for general retrieval.

Author:

The person who has taken the photograph.

Contributor:

The contributor could be the lab or person who developed the photo, or scanned it. Each contributor could have a role specified with a sub-element qualifier. Here we just mentioned the photo shop who scanned the photos.

Subject:

It should be a list of keywords, in a standard terminology for buildings and architecture. Since rural habitat has not yet attracted much interest as cultural heritage, there is no classification schema specifically relevant to these buildings. So we use common words (i.e. windows, roof, facade). Subject element is more intended for interoperability with other applications and we are not using it to query the metadata. Instead we use the sub-elements of the Description element since the photo will be retrieved only if there is a specific description for this subject.

Description:

Each photo has two descriptions: a general one usable in the presentation by village, and a more detailed using a scheme qualifier specific to the application. Our schema contains XML elements for the parts of the house that are being described (roof, roof windows, windows, doors, coating, front, etc..). It is also used to describe the general state of the building: renovated, poor condition, etc.

Publisher:

The publisher of the CD-ROM. There is a problem here if we want to make the material reusable: the publisher would depend on the specific application the photo is used in. In our case it was not clear what to put in. We chose to mention the Association who supports the creation of the CD-ROM, although the photos (and their metadata) could be reused in another context.

Date:

The date when the photograph was taken (not scanned). At this point it seems that Dublin Core requires to use Date for the date of the digital resource, and possibly source.date for the date of the original photo. For us it was typical of the problem that arises with photos. We would rather consider the photo as the resource, and the various digital images as surrogates for this photo. We will come back to this point with Format. For our application what is important is the date of the original photo which marks the state of the building at a determined period.

Type:

The type of the resource which is "photograph" in term of the DC resource categories. We also mentionned whether it was a colour or black and white photo, in a second type element.

Type.quality: The quality of the photo. There is no specific element in DC to speak about the intrinsic quality of an image or a photo. Although it may be somehow subjective, it is an important information when the user or the application want to make choice between equivalent photos to display. Puting it as a sub-element is certainely not conform to DC requirment for qualifier, but there was no appropriate place to add this information, using Dublin Core.

Format:

The format of the digitised image (MIME/JPG). Format.orientation: Whether the photo must be seen horizontally, or vertically. This is an important information when selecting photos for multimedia presentation, since vertical photos can be grouped differently as horizontal ones to fit in an usual screen size. Format.full and Format.small are referering to the existence of two surrogate formats for the photos. Again there was a difficulty here in describing various format/ size for the same photo.

Identifier:

a reference to the actual photo. We could not use an URL since the photos will move to a CD-ROM, with a different hierarchy. We use an URI that reflects the relative organisation of the application.

Source:

A reference to the original photo, or its negative; the value of the reference will strongly depend on where the original is archived, whether it is a personal collection or an Archive Department.

A specific SCHEME could be useful here.

Language:

Not applicable for photographs.

Relation:

Relation to the overall collection or to another photo for comparison. Relation could in principle be used for reference to surrogates of the same photo, but we did not like this solution which will make seaching for a photo a very complex process.

Coverage:

The date and location of the object in the photo (building).

Coverage.date:

The date of the object being photographed We did not use this element since we had little information on the construction date of the buildings.

Coverage.location:

The precise address of the building since the photo could serve as a future archive for the villages. We introduced an address scheme (number, street, village), to be able to retrieve and sort out the photos by village, street, or house.

Rights:

The copyrights for the photograph. There is some ambiguity between the rights for the source and for the digitised photograph. We mean here the source version, and by extension any digitised version of the photograph. Copyrights may be much more complex.

In resume the difficulty with metadata for photographs is to make the distinction between the information about the photo and the information about what is represented by the photo. Retrieval of the photo will be mostly done from the latter while rendering of the photo has nothing to do with its content. The existence of various "versions" or digital surrogates from the original photo makes it more confused, as reflected in the use of the Format element. These problems have been already identified in [Wei97].

Metadata for describing the scanning process

[BESS] makes strong requirements on what information should be kept on the format of a digitised image and on the scanning process. This information is mostly irrecoverable if not recorded at the time of the capture. In large archiving projects this would be a major requirement, while less critical for casual user or small applications such a CD-ROM. These information may be important to be able to display long term archive images in many years, or to create large photograph workbenchs. In our case

we did not store any information about the scanning process other than the name of the laboratory who did the work. We feel it was not necessary in regard to the type of photos and precision of the digitalised images.

Application specific metadata:

As said before, metadata specific to the application were introduced as extra tags in the various Description elements, using a Scheme qualifier. For example, the description of a "window" is expressed as follows:

<DC:Description Scheme ="habitat"> <Rural > <window example="good"> The windows are heigther than large (1/3), with 6 glasses.

Note the irregularity of the window disposal, with a large plain area on the right. </window> </Rural> </DC:Description>

For more complex applications this information could be stored in a separated XML document, with a possibly complex DTD. For simplicity, we choosed to store it in repeated Description elements.

Virtual Documents

Our CD-ROM will have a large number of pages, even for only 150 photographs since each photo may correspond to several presentations depending on the context where it is displayed. Moreover we intend to scan and add more photos in the future and design more personalised versions of the CD-ROM for didactic usage in a specific village. Clearly we need a tool to automate the creation of pages, which would allow to select photos and group them by themes, villages, etc.

Our solution is to generate pages as virtual documents, i.e. to write HTML "templates" with normal tags and text and with instructions on how to generate dynamic information extracted from the photograph collection. In this section we introduce Norfolk, our virtual document generator, give some examples of document prescriptions to generate our CD-ROM, and describe the set of prescriptions. We conclude with a discussion about dynamic generation.

The Norfolk system

Norfolk is a system for the generation of virtual documents. Initially developed to promote the idea of information reuse, it has been used for Web delivery (see [START_REF] Paradis | A Language for Publishing Virtual Documents on the Web[END_REF] to see how it is used to generate and maintain the TED Web Site), and more recently for customised information delivery, i.e. how to select, modify or generate the information to satisfy a particular user need.

In Norfolk, the instructions to generate a virtual document have a descriptive rather than a programmatic style, and, more importantly, a common data model is defined to view information coming from a variety of sources as a document-like structure. Information sources can still be queried in their native format (e.g. SQL for a relational database), but results are then "translated" to a tree structure similar to a document parse tree. A query language allows selection or modification of the tree, and supports useful operations for document structures. For example it supports extraction of semistructured information, i.e. information whose exact structure is not known or can vary. For more information on Norfolk data model and language, see [START_REF] Vercoustre | A Descriptive Language for Information Object Reuse through Virtual Documents[END_REF]. An online demonstration is also available at http://www.ted.cmis.csiro.au/RIO/.

Figure 3 shows how Norfolk is used to generate a set of pages. The instructions to generate the virtual documents are stored in document prescriptions. The interpreter takes a document prescription as input, queries data sources such as databases or other pages, and produces a virtual document as output. The "children" or document prescriptions referenced in the virtual document, are then recursively generated. In other words, the generator "follows" the links to document prescriptions in order to generate a network of virtual documents. Cycles and naming for the virtual documents are automatically dealt with.

Examples of prescriptions

The following example shows part of a prescription for collecting all the photographs related to one village (passed as a parameter) and to display the list of those photographs, with the address of the places and links to the actual photographs.

<!--Takes one parameter: the village name --> <?param "village" as $village> <!--Output title (village name) --> <H1> <?$village> </H1> <!--=== PART 1: find photos for village ===--> <!--Assign all filenames to $photos --> <?define $photos as url("DIR.xml")..f> <!--build $photosVillage (photos for a village) by iterating through the list of all photos --> <?map $xx in $photos> <?begin> <?define $a_photo as url(str("photos-XML/",$xx))> <?if $a_photo..town contains $village> <?begin> <?define $photosVillage as $photosVillage adopt $a_photo> <?end> <?end> <!--=== PART 2: output list of photos ===--> <ul> <?map $photo in $photosVillage> <li> <?$photo..Address.number;$photo..Address.street> <A> <?attributes attr("href",str("../",$photo..DC:IDENTIFIER)) > <?$photo..DC:SOURCE> </A> </li> </ul> The document prescription is a valid HTML document, to which Norfolk instructions are added in the form of process instructions (i.e. <?...>). "Part 1" finds the photographs for the village. It first gets the list of all metadata files (an index file, DIR.xml, which is dynamically generated, has an <f> element for every file) and then iterates through the list, loading the file and checking if it is in the right village. In practice, for efficiency reasons, the list of photographs for every village could be built beforehand, and included in DIR.xml. "Part 2" then outputs the photographs in a list, with the address and a link to the image for every photograph.

The following prescription produces a list of four villages, with a link to their respective page. The href attribute, created with the attr command, is a link to the village prescription. This link consists of the prescription name, village.rhtml, and the village name: for example, the urlstr command will produce village.rhtml?village=Chavenay). The attributes instruction is then used to attach the href attribute to the preceding tag, <A>. <html> <!--output list of links to each village page --> <ul> <?map $x in list("Les Alluets-le-Roi", "Chavenay", "Ecquevilly", "Noisy-Le-Roi")> <li><A> <?attributes attr("href",urlstr("village.rhtml","village",$x)) > <?$x> </A> </li> </ul> </html>

The set of prescriptions

Except for the static pages (introduction page, map, acknowledgment, etc.) that are not shown in Figure 1,--> Most pages in our application fall into one of the following models: Each model has to be designed carefully with possible variants. For example a page according to model 1 could be organised by streets if there are many photos for a village, or could display iconic photos in a unique page if there is only a small set of photos. Further links to individual photos will lead to pages generated according to model 2 or model 4, depending on the context.

It is worth to notice that model 2 and model 4 could be the same, with a parameter setting the context. It may be a quick way of prototyping the pages in a preliminary version of the CD-ROM.

Dynamic generation versus materialisation

The automatic generation of Web pages in Web-based Information systems can be either done in a dynamic mode or a compiled mode. Dynamic generation of pages arises when a page is created at the time an user tries to access it. The pages are kept virtual and never stored in a Web site. Usually the page is created by a specific program (for example a Common Gateway Interface, a CGI-script, to a database), or from a specific query language whose statements are embedded into HTML pages [START_REF] Vercoustre | A Descriptive Language for Information Object Reuse through Virtual Documents[END_REF]. Another approach is to compile all the pages into a materialised hypertext. Although for Web sites, one can argue with [START_REF] Sindoni | Incremental maintenance of hypertext views[END_REF] whether a dynamic generation is preferred to the creation of actual pages, for a CD-ROM there is no benefit in keeping the pages dynamic. The main reason is that once the information is on the CD-Rom there is no way of updating it, and therefore the generated pages will never change.

The dynamic generation is very useful though during the design and tuning of the page prescription, as well as during the process of selecting the appropriate photos, as we have explained before.

Comparison with other works

The main feature that distinguishes Norfolk from other approaches is that it is document-oriented. Virtual documents on the Web are usually generated through programs or scripts that sometimes can be embedded in an HTML document. This often means that the person responsible for the document (the creator) has to rely on someone else (the programmer) to deliver the information on the Web. Furthermore, these languages do not offer appropriate data types for the manipulation of document structures, which is crucial as virtual documents need to extract and include parts of other documents, or to render other information in a document-like manner.

The CD_ROM [START_REF] Rochelle | Patrimoine architectural et mobilier, CD-ROM[END_REF] about architectural heritage in La-Rochelle was produced by defining XML documents (according to an Inventory DTD) which were automatically translated into HTML using XSL. XML pages were translated according to XSL templates similar to our prescriptions. The difference is that our language can query several XML documents or other data sources, while XSL templates are applied to one XML page at time. It is a one page to one page translation.

The Araneus system [START_REF] Atzeni | Design and Maintenance of Data-Intensive Web Sites[END_REF] uses a page model language to define Web pages and typed links between pages. Content of pages can be extracted from various data sources and integrated through a nested table model. Although the definition of true typed links between classes of pages is interesting we think that our tree model and page prescription language fits better with the XML/HTML models and languages.

Conclusion

We have shown how XML metadata can support the retrieval of photographs and the generation of advanced presentations using these photographs. The cost of creating the metadata makes it important to make them reusable for a variety of purpose and extendable to a particular application. Dublin Core can be used for photographs after some adjustments, especially on the Format and Source elements. Dublin Core does have some limitations however when it comes to describing "surrogates", or when several photographs represent the same object.

Our approach with metadata has the following advantages:

r Being textual and external to the image, our metadata descriptions are easier to read and to modify. r We can use an SGML query language to search or extract metadata (here we have used Norfolk file:///T|/.public/www/DOCS/ECDL99/index.html (12 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris query language). r Our metadata scheme is extendable, as we have shown by extending the Dublic Core with qualifiers and simple schemas.

The generation of pages using virtual documents in our application has the following advantages:

r There is a considerable gain in time: instead of writing many similar pages, only one prescription has to be written. r The pages are less prone to errors. The photograph metadata and document prescriptions, are written and checked once, and reused many times. r There is a separation between information and delivery (ie. metadata and HTML pages), which allows to easily define several presentations of the same information r Norfolk can support the flexible generation of presentation from heterogeneous sources, which will be a requirement for the next generation of Digital Libraries.

Future work involves the definition of models for comparison that support the generation of queries for appropriate comparable elements, and the display of these elements.

Footnotes

[1] Searching by similarity with a given photos can be done using internal low level characteristics of the photo. We are not addressing this kind of search here.

Figure 1 :

 1 Figure 1: Structure of the CD-ROM

Figure 2 :

 2 Figure 2: Example of photosFull size image

Figure 3 :

 3 Figure 3: Generation of pages using Norfolk

Figure 4 :

 4 Figure 4: Document prescription for a Village

Figure 5 :

 5 Figure 5: Document prescription for a List of Villages

r

  model 1: set of photos organised by village (village.rhtml) r model 2: a page by (photo, context = village) r model 3: set of photos organised by themes; each theme may have its own model. r model 4: page by (photo, context = theme) (for the relevant photos) r model 5: full size photo

file:///T|/.public/www/DOCS/ECDL99/index.html (1 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (2 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (4 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (5 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (6 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (7 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (8 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (9 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (10 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (11 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (14 sur 15)27/07/2007 16:00:52 paper submission to EuroDL'99, Paris

file:///T|/.public/www/DOCS/ECDL99/index.html (15 sur 15)27/07/2007 16:00:52

Appendix: Example of XML metadata for the photograph "AH3"

<?xml version="1.0"?> <metadata lang="Fr"> <DC:Title> Maison rurale à Chavenay (78), France </DC:Title> <DC:Creator> Anne-Marie Vercoustre


Craig A Lindley
email: craig.lindley@cmis.csiro.au

Anne-Marie Vercoustre
email: anne-marie.vercoustre@inria.fr

Generic Viewer Interaction Semantics for Dynamic Virtual Video Synthesis

The FRAMES project is developing a system for video database search, content-based retrieval, and virtual video program synthesis. For dynamic synthesis applications, a video program is specified at a high level using a virtual video prescription. The prescription is a document specifying the video structure, including specifications for generating associative chains of video components. Association specifications are sent to an association engine during video synthesis. User selection of a virtual video prescription together with the default behavior of the prescription interpreter and the association engine define a tree structured search of specifications, queries, and video data components. This tree structure supports generic user interaction functions that either modify the traversal path across this tree structure, or modify the actual tree structure dynamically during video synthesis.

Introduction

The FRAMES project is developing a system for video database search, content-based retrieval, and virtual video program synthesis. The FRAMES project has been carried out within the Cooperative Research Centre for Advanced Computational Systems established under the Australian Government's Cooperative Research Centres Program. Video components within the FRAMES database are described in terms of a multi-layered model of film semantics, derived from film semiotics. For dynamic video program synthesis applications, a program is specified at a high level using a virtual video prescription (Lindley and Vercoustre, 1998a). Coherent sequences of video are required, rather than just lists of material satisfying a common description. To meet this requirement, the FRAMES system uses an engine for generating associative chains of video sequences, initiated by an initial specification embedded within a virtual video prescription. Once a virtual video prescription has been selected, the prescription interpreter and associated instruction processing functions can be allowed to generate a virtual video with no further interaction from the viewer. In this case the resulting presentation has the form of a traditional linear film or video. However, depending upon the viewer's overall purpose, it may be desirable to steer the ongoing presentation in various ways. For example, the user may wish to steer the presentation towards subjects of interest and away from those of less interest, gain an overview of the area, go into detail, or follow a particular mood or emotion.

This paper defines generic user interaction semantics for dynamic virtual video synthesis based upon the data structures and sequencing functions of the FRAMES system. The semantics provide run-time interactions for the viewers of a virtual video; the interactions do not result in any permanent changes to the data structures involved, but affect the way those data structures are used to generate a particular video presentation. We begin with a summary of FRAMES system users and user tasks, provide an overview of the FRAMES system, and summarise the processes that are used to select video components during the generation of a synthesised video sequence. The high level algorithm used within the FRAMES association engine is described, and is seen to define a tree-structured search through the available video components. User interaction semantics are then analysed in terms of generic user interaction strategies, the default data structure that models the selection action of the synthesis engine, and generic interaction operations that can be defined in terms of their effect upon the implied data structure.

FRAMES System Users and User Tasks

The FRAMES video synthesis process implies four different author/system user roles that may be involved in the production and use of a virtual video. Within the FRAMES system, video data is a primitive (atomic) data input, organised as a set of discrete video sequences. The video maker may use a variety of software tools and products to create these digital video clips. Interactive video systems that support interaction within a complete video program represent a new medium requiring customised development of video data.

The FRAMES video synthesis engine operates upon descriptions associated with raw video data. Hence once the video data is available, a description author must develop a descriptor set and associate descriptors with appropriate video data sequences. The FRAMES environment includes data modeling interfaces to support this authoring process. The interfaces and underlying database are based upon the semiotic model described by [START_REF] Lindley | Query Semantics for Content-Based Retrieval of Video Data: An Empirical Investigation[END_REF]. Once the descriptions have been created, they are stored in the FRAMES database for use by the video synthesis engine.

The FRAMES system can be used with these semantic descriptions to provide basic semantic search and retrieval services, where a user can directly interrogate the database using relational parametric queries, or interrogate the database via the FRAMES association engine either to conduct fuzzy parametric searches, or to generate an associative chain of video components. However, for many users and applications a specific high level program structure may be required. Such a structure can be defined using a virtual video prescription. A prescription, defined by a virtual video prescription author, contains a sequence of embedded queries for generating the low level video content, where the particular order, form, and content of the queries implements a specific type, genre and style of video production.

The final end user/viewer community is the audience for whom the virtual video production is created. Such a user will typically select a virtual video prescription according to their current tasks and needs, and use the FRAMES virtual video synthesis engine to generate a virtual video presentation. For dynamic virtual video synthesis, there are a number of ways and points in the process where viewer interaction is meaningful. All viewer interaction functions may be available to the authors of the interaction system, to provide feedback to authors about the appropriateness and effectiveness of descriptions and prescriptions as they are being developed. The authoring process for interactive virtual videos is highly complex, and requires careful coordination between the video makers, description authors, and prescription authors to ensure that these three levels of content are compatible and function correctly to produce coherent viewer sequences. Understanding the principles for doing this effectively is an important topic of ongoing research.

The FRAMES Video Synthesis System

The FRAMES system consists of three primary elements: a virtual video prescription interpreter, a database containing semantic descriptions of individual video components, and the instruction engines for generating sequences of video data. A virtual video prescription represents a high level structure of, or template for, a video program of a particular type, containing a list of instructions for generating a virtual video production (Lindley and Vercoustre, 1998a). The virtual video interpreter reads virtual video prescriptions. A user may select a prescription, which may have values assigned to various embedded parameters to reflect the particular requirements and interests of that user before being forwarded to the interpreter. The interpreter reads the instructions within a prescription sequentially, routing each instruction in turn to an appropriate processor. Three types of instructions may occur within a prescription: direct references to explicitly identified video components, parametric database queries, and specifications for generating an associative chain of video components [START_REF] Lindley | The FRAMES Processing Model for the Synthesis of Dynamic Virtual Video Sequences[END_REF]. Access by direct reference uses an explicit, hard-coded reference to a video data file plus start and end offsets of the required segment (eg. using the referencing syntax of SMIL, [START_REF] Hoschka | Synchronised Multimedia Integration Language (SMIL) 1.0 Specification[END_REF]. Parametric database queries may include complex logical conditions or descriptor patterns. In parametric search, the initial query may form a hard constraint upon the material that is returned, such that all of its conditions must be satisfied. Alternatively, a ranked parametric search can return a list of items ranked in decreasing order of match to the initial query, down to some specified threshold. Access by associative chaining is a less constrained way of accessing video data, where material may be incorporated on the basis of its degree of match to an initial search specification, and then incrementally to successive component descriptions in the associative chain. Associative chaining starts with specific parameters that are progressively substituted as the chain develops. At each step of associative chaining, the video component selected for presentation at the next step is the component having descriptors that most match the association specification when parameterised using values from the descriptors attached to the video segment presented at the current step. The high-level algorithm for associative chaining is:

1. initialise the current state description according to the associative chaining specification. The current state description includes:

• the specification of object, attribute, and entity types that will be matched in the chaining process, • current values for those types (including NULL values when initial values are not explicitly given or components of the next instantiation are NULL),

• conditions and constraints upon the types and values of a condition, and • weights indicating the significance of particular statements in a specification 2. Generate a ranked list of video sequences matching the current state description. 3. Replace the current state description with the most highly ranked matching description: this becomes the new current state description. 4. Output the associated video sequence identification for the new current state description to the media server. 5. If further matches can be made and the termination condition (specified as a play length, number of items, or associative weight threshold) is not yet satisfied, go back to step 2. 6. End.

Since association is conducted progressively against descriptors associated with each successive video component, paths may evolve significantly away from the content descriptions that match the initial specification. This algorithm (described in detail in Lindley and Vercoustre, 1998b) has been implemented in the current FRAMES demonstrator. Specific filmic structures and forms can be generated in FRAMES by using particular description structures, association criteria and constraints. In this way the sequencing mechanisms remain generic, with emphasis shifting to the authoring of metamodels, interpretations, and specifications for the creation of specific types of dynamic virtual video productions.

Generic Interaction Strategies

User interaction in the context of dynamic virtual video synthesis can take place at several levels, and in relation to several broad types of user task. Canter et al (described in [START_REF] Mcaleese | Navigation and Browsing in Hypertext[END_REF]) distinguish five discernible strategies that users may use in moving through an information space:

1. scanning: covering a large area without depth 2. browsing: following a path until a goal is achieved 3. searching: striving to find an explicit goal 4. exploring: finding out the extent of the information given 5. wandering: purposeless and unstructured globetrotting These strategies are all relevant to interaction with dynamic virtual video synthesis, and the interactive presentation system for virtual videos should support each strategy. To these five strategies we can also add: 6. viewing: allowing the algorithm to generate a video sequence without further direction from a user (ie. the viewer is passively watching a video)

Dynamic virtual video syntheses in the FRAMES project uses the viewing model as the default behavior of the system. That is, once a virtual video prescription has been selected, the synthesiser generates the video display based upon that prescription and the semantics defined by the underlying algorithms. The virtual video prescription may define a video program amounting to a scan, browse, search, exploration of, or wander through the underlying video database, depending upon the applicationspecific purpose of the prescription. To provide interactive viewing functions, suitable interfaces must be provided allowing viewers to modify the behavior of the video synthesis engine away from this default behavior within the form defined by the original virtual video prescription.

User Interaction Semantics

A prescription can be customised for a particular user by setting its parameter values. Parametric search may be an exact search mechanism (eg. if a traditional relational database is used), or may involve a fuzzy search process that returns identifiers of video component having descriptors that approximately match the search query, ranked in decreasing order of match to the query. A video synthesis system incorporating ranked search can include interfaces allowing users to select from the ranked list of returned results. Associative chaining can be modified in several ways by user interactions, by using user interactions to effectively modify the chaining specification dynamically as chaining proceeds. Users can modify the entity types used to associate the current component with the next component, modify the current entity values, set or reset constraints upon entity values, or modify the weightings upon entity types. Users can also interrupt the default selection of the most highly associated video component by selecting another ranked element as the current element, which will re-parameterise the associative chaining specification at the current point in the chain.

Fig. 1.

The semantics of these user interactions can be modeled by regarding the operation of the association engine as a tree search behaviour, as shown on Figure 1. In considering choices that can be made by users, it is useful to regard the starting point as the decision about which virtual prescription to execute, this being the root node of the search tree. Each prescription contains a list of instructions that constitute its child nodes. The algorithm that interprets prescriptions will execute each instructions in sequential order. An instruction (specifically, an instruction that is an association specification) generates a series of video components that are its child nodes in turn, each component being presented for display in the sequential order in which it is returned. Finally, for each selected video component in a series, there is a list of other candidate components that have not been selected, ranked in decreasing order of associative strength (to the previous component in the selected list); this ranked list may be considered to be a set of child nodes for a selected component. Hence the video synthesis process defines an ordered, depth-first traversal of the system data structures and the dynamically generated association structure of video components.

The default behavior of the synthesis engine without user interaction satisfies the user interaction strategy identified above as viewing. However, to support scanning, browsing, searching, exploring, and wandering strategies, specific and generic interaction functions can be provided. These are divided into two classes. The first class of interaction functions are those that determine the path taken by the user in traversing the default synthesis tree amount to functions that interrupt or modify the default depth-first traversal behavior of the algorithm. These functions include:

• control of whether the process should stop, loop back to some point (eg. as identified on a history list), or proceed to the next default item S2 S3 • jump to a position on the tree other than the next position defined by the depth-first algorithm • display a set of video components in parallel

The second class of interaction functions are those that dynamically alter the structure of the default tree during video synthesis are functions that effectively produce an alteration in the specification that is driving the generation of a virtual video production. This can include:

• functions that dynamically modify virtual video prescriptions (eg. changing the values of variables used within a prescription during execution) • functions that dynamically modify queries prior to their execution, or as they are being executed. Examples include adding or removing descriptor types that associative matching is taking place against, and modifying the weightings attached to descriptor types.

Related Work

Interactive video covers a broad range of technologies and interests, including interactive video editing systems, model-based video image generation, and interactive search and browsing of video data in archives or databases. The FRAMES project is addressing the interactive use of predefined video sequences. Dynamic access to predefined video using content-based retrieval techniques has generally been based upon an information retrieval model in which data is generated in response to a single query (eg. the IBM QBIC system, http:// wwwqbic.almaden.ibm.com/ stage/ index.html); sequencing from this perspective is a contextual task within which content-based retrieval may take place. The MOVI project has incorporated some automated video analysis techniques into an interactive video environment that then uses hard-coded links between video elements (see http:// www.inrialpes.fr/ movi/ Demos/ DemoPascal/ videoclic.html). Unlike these approaches, FRAMES generates links between video sequences dynamically using an associative chaining approach similar to that of the Automatist storytelling system developed at MIT [START_REF] Davenport | ConText: Towards the Evolving Documentary[END_REF][START_REF] Davenport | ConText: Towards the Evolving Documentary[END_REF][START_REF] Murtaugh | The Automatist Storytelling System[END_REF]. The Automatist system uses simple keyword descriptors specified by authors and associated with relatively self-contained video segments. In Automatist, users can interact with the associative chaining process either by explicitly modifying the influence of specific keyword descriptors arranged around the periphery of the interface, or by selecting a less strongly associated video component to become the current displayed component determining the ongoing associative chain. The FRAMES system extends this associative chaining approach by using a highly structured semantic model (described in [START_REF] Lindley | Query Semantics for Content-Based Retrieval of Video Data: An Empirical Investigation[END_REF], which allows greater discrimination on descriptor types, and more types of relationship between sequenced video components. Flexible and modifiable association specifications in FRAMES and the incorporation of direct references and parametric queries in high level prescriptions create opportunities for interaction beyond the simple selection of keywords and ranked components.

Conclusion

This paper has presented an analysis of the underlying semantics of user interaction in the context of the FRAMES dynamic virtual video sequence synthesis algorithms. Ongoing research is addressing the presentation of interaction options to users, and the problem of disorientation within the unfolding interactive video.


Nicolás Bordenabe
email: nicolas.bordenabe@mq.edu.au

Annabelle Mciver
email: annabelle.mciver@mq.edu.au

Carroll Morgan
email: carroll.morgan@unsw.edu.au

Tahiry Rabehaja
email: tahiry.rabehaja@mq.edu.au

Reasoning About Distributed Secrets

Keywords: Quantitative information flow, foundations of security, program semantics, secure refinement

Introduction

This paper concerns information flow when secrets are distributed amongst several agents. For example, let X, Y and Z represent three agents with respective secrets x, y and z, where z = f(x, y) for some function f. In this basic scenario, each secret is correlated via a known function (f), so that if something is leaked about one of the secrets, then something is also leaked about the others.

Partial disclosure about one secret leading to collateral disclosure about another is well documented in privacy of statistical databases, and was first addressed by Dalenius [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF] who argued that ideal designs for privacy should prevent it: "Nothing about an individual should be learnable from the database that cannot be learned without access to the database". Later he argued the infeasibility of such a strict goal, and more recently Dwork [START_REF] Dwork | Differential privacy[END_REF] addressed the same concern demonstrating that whenever there is a (known) correlation between two pieces of information, anything learned about one piece implies that something might also be learned about the other.

In secure programming generally, i.e. not just read-only databases, this corresponds to leaking information about a secret "high-level" variable x, which then consequentially leaks information about a different high-level variable z that does not appear in the program at all, but is known only via "auxiliary information" to be correlated with the initial value of x (as in z = f(x, y) mentioned above).

Because of the generality of this programming-language perspective, we call this effect collateral leakage.

Our approach is information theoretic where we model secrets as probability distributions DX over some secret space X , and we assume that programs are mechanisms which can both update secrets and leak some information about them. Within this setting we study the broader phenomenon of collateral leakage where secrets might be distributed between several non-colluding agents, and where those secrets could be correlated.

We extend our recent work by using Hidden Markov Models (HMM 's) in a new way to handle collateral leakage. In particular we study how to analyse the system-wide impact of information leaks caused by program execution on some, but not all of the secrets. These issues have been addressed partially in other work, but here we bring all these results together and take them further. In summary, we do the following:

• We review standard HMM 's and show how to view HMM matrices as mappings from correlations expressed as distributions in DX 2 to correlations DX 2 , when the HMM is only able to update the second component in the product X 2 ( §3.2). • We show how this unusual view of HMM 's -as mechanisms that update correlations-can be used to study the impact of information flow on correlated secrets, even when those secrets are not mentioned in particular program fragments ( §4), and we provide methods to calculate exact and approximate leakages. Full proofs of these results can be found at [START_REF] Bordenabe | Compositional security and collateral leakage[END_REF]. • We illustrate some of our results on the analysis of a defence against side channels in cryptography ( §5).

A particular novelty of this approach is "security refinement" which determines a partial order on HMM 's extending previous work [START_REF] Mciver | Abstract Hidden Markov Models: a monadic account of quantitative information flow[END_REF] to HMM 's as correlation transformers. Refinement allows programs to be compared in a compositional manner: this does not seem possible with less general notions of leakage [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF].

2 Motivation: correlated passwords 2.1 Changing a password: is it only "fresh", or actually "different"?

The example of Fig. 1 contrasts two users' approaches to updating their passwords; for simplicity each password is just one letter, chosen from {A, B, C}. User Lax may update to any of the three, uniformly at random, including his current one; but User Strict must change his password, again uniformly, now choosing from only two of course. Because the original password X was uniformly distributed (which we assume for simplicity), in both cases the distribution of its final value is uniform as well; but an important difference, as we will see, is that for Lax the final X is independent of the initial X, while for Strict it is correlated. In the second statement, at †, we confront (hostile) information flow: both users suffer an "over the shoulder" attack while logging in with their new password.

"Lax" user X:∈ [A,B,C] * leak [X + ,X -] † "Strict" user X:∈ [X + ,X -] $ leak [X + ,X -] † * [...]
is a uniform distribution over {...}; and X:∈ chooses X from it. $ X + is the letter following X in X (wrapping around), and X -the preceding. † leak [...] chooses a value from the distribution [...] and passes it to the adversary: she does not know however whether that value was X + or X -.

Fig. 1: Updating a password

We imagine that an observer hears a key-click and sees a key that is not being pressed: she thus learns one value that the new password definitely isn't. Fig. 1 illustrates our concerns in a very simple way: the secret (password) is updated, and it is its final value the adversary wants to capture (indeed she will not be using its old value to hack this account). And yet -as we will see-third party agents can be affected.

One reason that in Fig. 1 it's natural to focus on the final state is that our aim (in program semantics) is to integrate security "correctness" with (ordinary) functional correctness of programs, i.e. to treat the two within the same framework [START_REF] Mciver | Abstract Hidden Markov Models: a monadic account of quantitative information flow[END_REF]; and since functional correctness (and correctness comparisons, i.e. refinement [START_REF] Morgan | Programming from Specifications[END_REF]) is determined wrt. the final values a program produces, we should do the same for security correctness. Indeed it is in both cases the concentration on final values that allows small state-modifying programs, whether secure or not, to be sequentially composed to make larger ones [START_REF] Mciver | Compositional closure for Bayes Risk in probabilistic noninterference[END_REF][START_REF] Mciver | Hidden-Markov program algebra with iteration[END_REF][START_REF] Mciver | Abstract Hidden Markov Models: a monadic account of quantitative information flow[END_REF]. Now the example above was constructed so that the two programs have the same final distribution and the adversary has the same knowledge of it -in both cases she knows exactly one value that the password is not. So are these programs equivalent in terms of their functional-and information-flow behaviour?

Here is where we encounter our criterion. As closed systems with a single secret, the password stored in variable X, Lax/Strict are indeed equivalent programs when the initial distribution is uniform. But they are not equivalent if we consider correlations between X and some other variable not mentioned in either, but present in a larger system with secrets distributed amongst other users. For example, suppose our young user selected his password X to be "the same as Dad's" that is stored in variable Z. And suppose Mum knows he did so.

So Dad says "You'd better change your password, son. Making it the same as someone else's is not safe." But as luck would have it Mum is in the bedroom, later, when Son changes it, and sees one of the two values that it has not become. In that case son Lax would leak no information about Dad's password; but with Strict, Dad's password is twice as likely ( 1 /2) to be what Mum saw as it is to be one of the other two values ( 1 /4 each). (See (8) below for details.)

Can this simple, almost fanciful example be dismissed? We don't think so: the facts are indisputable, that in the Strict case Mum learns something about Dad's password but in the Lax case she does not: we return to this in §3.2; and we give a more elaborate example in §5. Have we invented this problem? No: it was recognised by Dalenius [START_REF] Dalenius | Towards a methodology for statistical disclosure control[END_REF] and formalised by Dwork [START_REF] Dwork | Differential privacy[END_REF]. But (we believe) its impact has not been studied in respect of program refinement.

We stress the point that this phenomenon is truly remarkable if placed in the context of rigorous reasoning about programs generally. We have (var X; Lax) and (var X; Strict) are the same over uniform initial X (1) but (var Z; var X:= Z; Lax) and (var Z; var X:= Z; Strict)

are different over uniform initial Z (2)
What kind of familiar program algebra would invalidate an equality (1) because of variables added (2) that are not referred to by either program? The semantics of Lax and of Strict must differ in (1) as well.

In our extended HMM model described next, we show how Lax and of Strict are indeed modelled differently by keeping track of how programs change the correlation between initial and final program state. (In this case Son's initial and final passwords.) 3 HMM 's: generalising channels for secure refinement

Systems with distributed secrets

In a system of distributed secrets different secrets are handled by different system commands, possibly by different system components. Our aim here is to study the impact those commands have on all system secrets, whether or not they are part of any particular command. There are two reasons why this is important. The first is related to the issue raised by Dalenius, that a rigorous analysis of security must consider the prospect of the mechanism being executed in an environment where other secrets can be impacted. The second is related to compositionality in program semantics -the semantics must include enough detail so that conclusions drawn from local analysis of program fragments in isolation will be consistent with any emergent behaviours when those fragments are executed in larger contexts.

In our use of HMM 's detailed below we concentrate on showing how to use an analysis of an HMM in a compositional way -i.e. the analysis not only informs us about the leaks and updates to the variables described in a particular HMM matrix, but allows us as well to draw conclusions about leaks of other correlated variables if we consider the HMM to be executed as part of a larger system.

Review of the channel model for quantitative information flow

Traditional models of information flow use "channels" to model flows in so-called "mechanisms", i.e. stochastic matrices which describe the relationship between secrets of type X and observations of type Y. We recall first the standard notions of information flow in this setting, which we then extend to HMM 's.

Given channel matrix C, the entry C xy is the probability that y is observed given that the secret is x. Channel matrices are stochastic meaning that for each x, y: Y C xy = 1. We write α β for the type of stochastic matrices over α×β, thus C is of type X Y. A fundamental assumption is that the secret x, once set, never changes and the measurements of information flow that the channel model supports thus involve comparisons between the attacker's prior knowledge of the secret, and how that changes to posterior knowledge when observations Y are taken into account. The prior knowledge is captured by a probability distribution π: DX which assigns a probability π x to each possible value x: X ; posterior distributions emerge when π is combined with C and are calculated using Bayesian reasoning. For observation y and prior π, the posterior probability that the secret is x given observation y is C xy ×π x /( x : X C x y ×π x ). The vulnerability of a secret wrt. leaks can be assessed by measuring the extent to which the attacker can use the information leaked.

Notions of vulnerability of secrets and leakage of channels

Vulnerability is a generalisation of entropy (of distributions), no longer necessarily e.g. Shannon but now others more adapted for secure programming, and whose great variety allows fine-grained control of the significance of the information that might be leaked [START_REF] Mário | When not all bits are equal: Worth-based information flow[END_REF].

Given a state-space X , vulnerability is induced by a gain function over that space, typically g of type G W X = W→X →R, for some space of actions w: W. When W is obvious from context, or unimportant, we will omit it and write just g: GX . Given g and w (but not yet x) the function3 g.w is of type X →R and can thus be regarded as a random variable on X . The range of W models a set of actions available to the attacker and the value g.w.x represents his gain if he picks w and the secret's value turns out to be x. His optimal average gain, or g-vulnerability is then V g [π] = max w∈W x:X g.w.x×π x .

A particularly simple example is W=X with g.w.x = (1 if w=x else 0) so that the adversary gains 1 if he guesses correctly and 0 otherwise: we call this particular gain-function g id . A benefit of the more general W's is that they allow representation of many conventional entropy functions (including even Shannon), thus bringing them all within the same framework [START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF]. Given a g, prior π and a channel C we can model the expected conditional g-vulnerability as the maximal gain wrt. the channel C, or the average of the vulnerabilities of the posteriors:

V g [π, C]:= y: Y max w: W C xy ×π x ×g.w.x . (3)
Inspired by mutual information, we can define more general notions of leakage by comparing the g-vulnerability of a prior with the expected conditional vulnerability. The multiplicative g-leakage of C wrt prior π and gain function g is the ratio between the posterior and prior g-vulnerabilities:

L g (π, C) := log 2 V g [π, C]/V g [π] . (4)
The capacity of a channel is the supremum of that leakage (4), but varying in its definition depending on whether the supremum is over either gain functions, or priors or both:

L ∀ (π, C) := sup g L g (π, C) , L g (∀, C) := sup π L g (π, C) , L ∀ (∀, C) := sup π,g L g (π, C) .
Remarkably, it can be shown that L ∀ (∀, C) equals L g id (∀, C) ("min-capacity"): it is the most robust estimation of leakage, and can always be achieved for the uniform prior [START_REF] Mário | Additive and multiplicative notions of leakage, and their capacities[END_REF], making it straightforward to calculate. Moreover L g id (∀, C) (also called ML(C)) provides an upper bound for information leakage computed from the traditional Shannon entropy. Thus if ML(C) is no more than k then this means that no more than k bits are leaked by C for any prior. Capacities are useful because if they can be computed for a given channel C we are able to argue that the channel's leaks are insignificant if its calculated capacity is small.

HMM 's leak information about secrets and update them

The original model for HMM 's describes a two stage process acting on a secret in DX : first information about the secret is leaked, and then the value of the secret is updated. The first stage is equivalent to the action of a channel as described above, and the second stage is effected by a Markov transition. A Markov transition is also described by a matrix M (say) so that M xx is the probability that initial state x will result in final state x . An HMM-step then comprises a channel and a transition together, but acting independently on the initial state: we call C its channel and M its markov (lower case), and write (C:M ) of type X Y×X . Defined (C:M ) xyx = C xy ×M xx , it is a stochastic matrix with rows X and columns Y×X . In this way HMM 's generalise both Markov processes and channels, and can therefore model a program that both leaks secrets and updates them. We shall, in particular, study how to use HMM 's when there are distributed secrets.

We begin by generalising HMM steps in order to model behaviour of programs consisting of multiple leak and assignment steps. We define sequential composition for HMM 's which summarises the overall information flow: in fact sequential composition is a natural operator if we are using them to model programs. Let H 1,2 of the same type X Y×X be HMM 's.The composed type is the X Y 2 ×X that takes initial state x to final state x via some intermediate state x , leaking information (y 1 , y 2 ) -as it goes-gradually into the set Y 2 . We define

(H 1 ; H 2 ) x(y 1 y 2 )x = x H 1 xy 1 x ×H 2 x y 2 x , (5)
and note that it is again stochastic. Sequential compositions are strictly more general than the HMM -steps built directly from (C:M ) -that is, for some arbitrary composition (5) it does not necessarily correspond to a single step (C:M ) for some C and M .By keeping track of sequences of observations compositions of HMM -steps allow observers to accumulate multiple leaks over time and to draw conclusions based on their amalgamated knowledge. Returning now to our example at Fig. 1 we illustrate how a program can be modelled as an HMM, by composing individual HMM steps. Recall the program snippet X:∈ [X + ,X -] ; leak [X + ,X -] where first X is updated and then something is leaked. The first statement X:∈ [X + ,X -] corresponds this Markov matrix X X :

M S1 :   A A 0 B 1 /2 C 1 /2 B 1 /2 0 1 /2 C 1 /2 1 /2 0  
For Strict the output for each initial state is a uniform choice over anything but the input. As an HMM we write it (I c :M S1 ), where I c is the identity channel that leaks nothing.

The second statement leak [X + ,X -] corresponds to a channel matrix in X Y, where in fact Y=X because the observables are of the same type as the state:4

C 2 :   A •A 0 •B 1 /2 •C 1 /2 B 1 /2 0 1 /2 C 1 /2 1 /2 0  
This leaks uniformly any value not equal to the current state, and •A, •B, •C denote the observations. We write it as (C 2 :I m ), where I m is the identity Markov process that leaves all states unchanged.

For Strict the result is this HMM using (5) to form the composition (I c :M S1 ); (C 2 :I m ), we can write it as a single matrix X Y×X :

•A • B • C   A B C A B C A B C A 0 1 /4 1 /4 0 0 1 /4 0 1 /4 0 B 0 0 1 /4 1 /4 0 1 /4 1 /4 0 0 C 0 1 /4 0 1 /4 0 0 1 /4 1 /4 0  
The labels •A, •B, •C denote the observations corresponding to those from C 2 . Notice that the rows are not identical, because the first HMM -step updates the state in a way dependent on its incoming value.

Observe that there is a great deal of information concerning the current and former values of X: for example, if the secret was originally uniformly distributed over the three values, and if •A is observed, then the probability that the initial state was A but is now B is 1/4. Preserving this information about initial and final correlations in the semantics is precisely how we can analyse the effect that leaks about X has on other variables (such as Z in Fig. 1). We therefore consider HMM 's to be transformers not of individual secrets, but rather of secret correlations in DX 2 . When an HMM transforms a correlation, the first component remains unchanged, but the second is updated, as before, according to the HMM. Thus given a correlation between X of type X and some other secret X' (of the same type) the HMM now produces a joint distribution X ×Y×X which describes the correlation between the (unchanged) X', the observations, and the updated X. Definition 1. Given an HMM H of type X Y×X , and a distribution Π ∈ DX 2 , we write Π H: DX ×Y×X for the joint distribution defined:

(Π H) x0yx := x : X Π x0x ×H x yx . (6)
The probability that y is observed is p y := x0,x (Π H) x0yx . Given that y is observed, the (posterior) probability that the correlation is now (x 0 , x) is defined by: (Π H) x0yx /p y .

When Π * is the correlation Π * (x0,x) = 1/3 if and only if x 0 = x, then (Π * Strict) allows us to compute the chance that the correlation between initial and final values, given that A is observed: in that case the chance that initial state was A and the final is now B is 1/4, but the chance that the final state is the same as the initial is 0.

Next, we extend the definition of refinement of abstract HMM 's in closed systems [START_REF] Mciver | Compositional closure for Bayes Risk in probabilistic noninterference[END_REF][START_REF] Mciver | Abstract Hidden Markov Models: a monadic account of quantitative information flow[END_REF] to take correlations into account.

Definition 2. Let H 1 : X Y 1 ×X and H 2 : X Y 2
×X be HMM's over base type X with observation types Y 1 , Y 2 respectively. We say that H 1 H 2 if and only if there is a refinement matrix R:

Y 1 Y 2 such that H 1 • R = H 2 , where H 1 • R := y: Y 1 H 1 xy ×R y . 5
A special case of a refinement matrix R is given by y → y * for fixed observation y * -this removes all information flow in H so that H • R is maximal in the refinement order and therefore only records state updates. We write mkv.H for this maximal refinement of H. 6 7 Def. 2 has an equivalent formulation in terms of gain functions: H 1 H 2 means that the gain for an attacker of H 1 will always be at least as high as a gain for an attacker observing H 2 , because he can use the extra observations to improve his strategy. Note however that the attacker's gains are related to guessing the correlation. Given an HMM H and gain function g, we define

V g [Π, H] := y: Y max w: W x,x ,x Π xx ×H x yx ×g.w.(x, x ) . (7)
Theorem 1. Let H 1 , H 2 be HMM's. We have

H 1 H 2 if and only if V g [Π, H 1 ] ≥ V g [Π, H 2 ]
, for all g: W→X 2 →R, and Π: DX 2 .

If we use an initial correlation Π (x,x ) = 1/3 if and only if x = x , we see that Lax Strict since V gcid [Π, Lax] = 1/6 whereas V gcid [Π, Strict] = 1/4. Here gcid corresponds to gid, but where W = X 2 . Similarly Strict Lax since

V [AA] [Π, Lax] = 1/9 but V [AA] [Π, Strict] = 0,

Reasoning about distributed, correlated secrets

We return now to a system of distributed secrets described by X and Z, and we study how to model information flow about Z when only X is updated by a program fragment. Given an HMM H : X Y×X representing such a fragment, we can describe the effect that H has on some initial correlation Π : D(X ×Z) between X and Z by computing the joint distribution J: D(Z×Y×X ):

J zyx := x : X Π zx ×H x yx . Moreover Thm. 1 implies that if H H then V g [Π, H 1 ] ≥ V g [Π, H 2 ], for g: W×Z×X → R.
We show next that robust upper bounds for leakage Z follows from leakage about the initial state of X .

Define Π to be the Z-marginal of Π, i.e. Π = x: X Π xz and let matrix

Refinement of collateral channels and their corresponding HMM

's is consistent. Lemma 2. If H 1 H 2 then V g [π, chn.H 1 ] ≥ V g [π, chn.H 2 ]
  A •A 1 /2 •B 1 /4 •C 1 /4 B 1 /4 1 /2 1 /4 C 1 /4 1 /4 1 /2  
We see now clearly that Mum's best guess for Son's initial setting of his password is to guess the value she observes; she has now learned something about Dad's current password.

(

) 8
The simplicity of Defns. n of the H n just before -we can abstract only at the very end.

In the special case however where each H is an HMM -step (C n :M n ), the calculation of the effective channel can be somewhat decomposed.

); H) = C (M •chn.H) where in general (C 1 C 2 ) x,(y 1 y 2 ) = C 1 xy 1 ×C 2
xy 2 is parallel composition of channels. The M cannot be discarded, since it affects the prior of the "tail" H of the sequential composition. We see in the example above that we do not have to construct the full HMM, and then reduce it as we did at (8) but instead just perform the matrix multiplication of its components, so that chn.Strict = M S1 •C 2 . Even with Lem. 3, in general chn.H can be challenging to compute because its size (given by the number of columns in the stochastic matrix representation) grows exponentially with the number of single-step HMM 's, in the definition of H, that have nontrivial channel portions. We give an example of such a calculation in §5 (fast exponentiation for cryptography).

On the other hand, if we want to compute only the collateral capacity, we can obtain at least an upper bound at considerably less cost, without the need to compute chn.H exactly. The following provides an upper bound for L ∀ (∀, chn.H), and requires only linear resources. Lemma 4. For any H let CCap.H be defined

CCap. (C:M ) = L ∀ (∀, C) if H=(C:M ) CCap. ((C:M ); H ) = L ∀ (∀, C) + min(L ∀ (∀, M ), CCap.H ) if H=(C:M ); H Then L ∀ (∀, chn.H) ≤ CCap.
H with the stochastic matrix M treated as a channel.

In fact Lem. 4 provides a very robust estimate of the collateral capacity of an HMM, since it does not mention Z or the correlating Π. And it is the best possible general bound, achieving equality for some examples, e.g. Fig. 1: CCap for Strict is log(3/2), and for Lax it is log 1 = 0, confirming that Strict leaks some information about correlated secrets whereas Lax leaks nothing. Both these values are equal to the calculated leakages in their given scenarios. It is also easy to calculate since for any channel we have from [START_REF] Mário | Additive and multiplicative notions of leakage, and their capacities[END_REF]

that L ∀ (∀, C) = L g id (Υ X , C),
where Υ X is the uniform prior on X . In cases where we know the correlation Π (and thus Z), we can compute the collateral capacity by identifying the optimising gain function in Def. 4.

Theorem 2. Given H and Π: D(Z×X ) with Π, Π resp. the marginals of Π on Z, X ; define conditional ⇒ Π as above. There exists ĝ: G Z Z and ĝΠ : G Z X such that

L ∀ ( Π, ⇒ Π•chn.H) = L ĝ ( Π, ⇒ Π•chn.H) = L ĝΠ ( Π, chn.H) .
This shows that it is possible to construct the gain-function that maximizes the collateral capacity, and even allows its exact calculation. Moreover, it also shows that the collateral capacity of H wrt. Z can be understood as regular g-leakage of H wrt. the initial state of X .

The next theorem is more general, and gives an upper bound over all possible correlations: it is determined by the extremal leakage of the initial prior π: DX , thus easy to calculate [START_REF] Mário | Additive and multiplicative notions of leakage, and their capacities[END_REF].

Theorem 3. Given H and Π as above, Υ X is uniform on X , then

L ∀ ( π, ⇒ Π•chn.H) ≤ L g id (Υ X , chn.H) , where π, ⇒ Π are as defined in Thm. 2.
Note that when X,Z are completely correlated, i.e. when ⇐ Π and ⇒ Π are both the identity, the inequality in Thm. 3 becomes equality. Finally we note that the separation of information flow from state updates sometimes does simplify sequences of HMM steps, when either the chn.H or mkv.H contains no probabilistic updates, then the channel can be approximated by (chn.H : mkv.H). We provide details at [START_REF] Bordenabe | Compositional security and collateral leakage[END_REF].

Case study: side channel analysis

Keys for public-key cryptography are best if independent, but that is not to say that they necessarily are: recently [START_REF] Arjen | Ron was wrong, Whit is right[END_REF] discovered an unexpected sharing of the prime numbers used to generate them. Although that discovery concerned public keys (and hence also the private keys), it makes the point that we cannot assume not-yet-discovered correlations do not exist between private keys alone. That motivates our example here, the collateral leakage from a fast-exponentiation algorithm that might compromise someone else's private key.

// B for base, the cleartext; E for exponent, the key: precondition is B,E >= 0,0 . // P for power, the ciphertext. Although our state comprises B,E,P,D,R we concentrate only on the secrecy of E. In particular, we are not trying to discover B or P in this case; and D,R are of no external significance afterwards anyway.

Fig. 2: Defence against side channel analysis in exponentiation, Exp(B,E) Fig. 2 implements fast exponentiation, with a random choice of divisor to defend against a side channel that leaks program flow (of a conditional) [START_REF] Walter | MIST: an efficient, randomized exponentiation algorithm for resisting power analysis[END_REF]. Since the program code is public, that leak is effectively of whether divisor D exactly divides the current value of E, which value is steadily decreased by the update at the end of each iteration: thus additional information is leaked every time. In the standard (and fastest) algorithm the divisor D is always 2, but that ultimately leaks E's initial value exactly, one bit (literally) on each iteration. The final value of E is always zero, of no significance; but its initial value represents collateral leakage about subsequent use of this same key (obviously), but also the use of other apparently unrelated keys elsewhere [START_REF] Arjen | Ron was wrong, Whit is right[END_REF]. The obfuscating defence is to vary the choice of D unpredictably from one iteration to the next, choosing it secretly from some set D, here {2, 3, 5} although other options are possible. The divisor D itself is not leaked.

Since the output of Exp(B, E) of Fig. 2 is a function of its inputs, and as mentioned above its behaviour can be summarised by a single-step HMM, of the form (chn.Exp(B, E):"Output B E "). Thus our task is to compute chn.Exp(B, E). We modelled the loop as a sequential composition of HMM -steps for a fixed number of iterations and used Lem. 3 to construct a channel that captures the leakage of information about the initial state of the program. We assumed that all variables are secret, and that every iteration leaks some information at the if statement "if R!= 0", revealing whether the (hidden) R at that point is 0 or not, and therefore possibly information about the other variables too. Interesting however, is that although this leak appears to be standard, the obfuscation provided by the choice of R means that overall the calculation of chn.Exp(B, E) shows that the information leak is highly probabilistic, the more randomness provided by D. We provide detailed calculations in [START_REF] Bordenabe | Compositional security and collateral leakage[END_REF] of the construction of the HMM 's. Although our calculation is wrt. the uniform prior on E, and even though we do not know the extent of any correlation between this key E and others used elsewhere, by using the multiplicative capacity [1, Sec VI.C], we can bound the maximum leakage about the initial value of E with the min-capacity of such a channel. Furthermore, by relying on Thm. 3 we can see that this min-capacity can also be used as a bound on the collateral leakage with respect to any other secret that might be correlated to E. For example, if E has 8 bits then a maximum of 3.51 of those bits of E's initial state will be leaked; moreover no more than of 3.51 of bits of any other secret Z in the system, that could be correlated to E will be leaked. This is therefore a very robust upper bound on the impact of system-wide leakage. Our table Fig. 3 confirms that the larger the divisor set D, the less effective is the side channel; and the protection is increased with more bits for E.

Related work, conclusions and prospects

In this paper we have studied information leakage in systems where several secrets are distributed across a system. We have demonstrated how to use an HMM model to analyse collateral leakage in programs where some, but not all, secrets can change. We have shown that when correlations are present across the system, the impact of collateral leakages can still be predicted by local reasoning on program statements that process particular subsets of secrets. Our model represents the first step towards a general method for analysing leakages in distributed contexts.

Our work extends classical analyses of quantitative information flow which assume that secrets do not change. Early approaches to measuring leakage are based on determining a "change in uncertainty" of some "prior" value of the secret -although how to measure the uncertainty differs in each approach. For example Clark et al [START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF] use Shannon entropy to estimate the number of bits being leaked; and Clarkson et al [START_REF] Michael | Belief in information flow[END_REF] model a change in belief. The role of capacity when the prior is not known was stressed by Chatzikokolakis et al [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]. Smith [START_REF] Smith | On the foundations of quantitative information flow[END_REF] demonstrated the importance of using measures which have some operational significance, and this idea was developed further by introducing the notion of g-leakage to express such significance in a very general way. The partial order used here on HMM 's is the same as the g-leakage order explored in by Alvim et al [START_REF] Mário | Additive and multiplicative notions of leakage, and their capacities[END_REF], but it appeared also in even earlier work [START_REF] Mciver | Compositional closure for Bayes Risk in probabilistic noninterference[END_REF]. Unlike information flows that eg only use Shannon entropy, our based on gain functions respects composition of programs, making it suitable for equality reasoning in algebras [START_REF] Mciver | Abstract Hidden Markov Models: a monadic account of quantitative information flow[END_REF].

More recently Marzdiel et al [START_REF] Mardziel | Quantifying information flow for dynamic secrets[END_REF] analysed information flow of dynamic secrets, using a model based on probabilistic automata. This reflects a view that in general systems secrets are not necessarily static. In other work [START_REF] Mciver | Abstract Hidden Markov Models: a monadic account of quantitative information flow[END_REF] we have explored a model based on the analysis of final states only, but it cannot be used to explore general correlations with fresh variables, as we do here.

Clark et al [START_REF] Clark | Quantified interference for a while language[END_REF] give techniques for static analysis of quantitative information flow based on Shannon entropy for a small while-language. Extended HMM 's for modelling side channels have been explored by Karlof and Wagner [START_REF] Karlof | Hidden Markov Model cryptanalysis[END_REF] and Green et al [START_REF] Green | Further Hidden Markov model cryptanalysis[END_REF] for e.g. key recovery. We note that in §5 our quantitative capacity bounds on side channels are valid even for collateral leakage, when the program is executed as a procedure call. In §5 we observe that there is a relationship between reducing the impact of a side channel and the performance of the algorithm. Others [START_REF] Doychev | Rational protection against timing attacks[END_REF] have explored this trade-off between confidentiality and performance using a game theory setting.

Bordenabe and Smith [START_REF] Nicolás | Correlated secrets in quantitative information flow[END_REF] explore collateral leakage in the context of a static secrets, and our work can be seen as a generalisation of their approach when secrets can be updated. Kawamoto et al. [START_REF] Kawamoto | Compositionality Results for Quantitative Information Flow[END_REF] also study gain function leakage for complex systems made from components. Their focus is different to ours in that they consider how to decompose a channel in order to compute the leakage more easily; they do not deal with the general problem of collateral leakage.

Definition 3 .

 3 be given by ⇒ Π zx = Π xz / Π z if Π z > 0 and 0 otherwise. This factors Π into its marginal and a conditional, and indeed Π xz = Π z × ⇒ Π zx . Now the matrix multiplication ⇒ Π•H gives an HMM of type Z Y×X . Since we are interested in the leakage about Z only we can define a channel on Z alone by forgetting the final value of X . This gives us the "effective collateral channel". The effective collateral channel of H, written chn.H, is a stochastic matrix of type X Y and defined simply by ignoring the final state: thus (chn.H) xy := x H xyx . Definition 4. The collateral leakage resp. capacity of H wrt a prior Π: D(Z×X ) is the collateral leakage resp. capacity of ⇒ Π•chn.H.

  for g: W×X →R and π: DX . Proof. Define Π * xx := π x if and only if x = x . Observe now that V g [π, chn.H 1 ] = V g * [Π * , H], where g * .w.x.x = g.w.x.x. The result now follows by Thm. 1. Using Def. 3 on the HMM (I c :M S1 ); (C 2 :I m ) described above, we can calculate the effective collateral channel for the program Strict. It describes the information leak about the initial state of Son's password only. chn.Strict :

Lemma 3 .

 3 Let H be an HMM and (C:M ) an HMM-step. Then chn. (C:M ) = C chn. ((C:M

Lemma 5 .

 5 Let H, H : X Y×X be HMMs. CCap.H=0 ⇒ CCap.(H ; H)=CCap.H . Proof. From Thm. 4 the unfolding of the recursive definition for CCap.(H ; H) will eventually yield a minimum between non-negative terms which include CCap.H. The result now follows, because this allows a simplification to CCap.H .

  P:= 1 while E!=0 // Invariant is P*(B^E) = b e , where b, e are initial values of B,E . D:∈ [2,3,5] // D for divisor; uniform choice from {2,3,5}. R:= E mod D; // R for remainder. if R!=0 then P:= P*B^R fi // Side-channel : is E divisible exactly by D ? B:= B^D // D is small: assume no side-channel here. E:= E div D // State update of E here. (No side-channel.) end // Now P=b e and E=0: but what has an adversary learned about the initial e ?

Fig. 3 :

 3 Fig. 3: Collateral leakage in bits wrt E for different D's, for Prog given at Fig. 2.

  3,4 conceals that it can be difficult in practice to calculate the collateral leakage of an HMM. One reason is that a model for initial state only is not compositional i.e. chn.(H 1 ; H 2 ) cannot be calculated from just chn.H 1 and chn.H 2 alone. This implies that if H is expressed as a sequential composition of many smaller ones, e.g. if we have H = H 1 ; H 2 ; • • • ; H N , still the final states of the intermediate H's must be retained, not only to form the composition, but because the overall y observation from H comprises all the smaller observations y 1 • • • y N with each y n+1 being determined by the final state (x )

We write dot for function application, left associative, so that function g applied to argument w is g.w and then g.w.x is (g.w) applied to x, that is using the Currying technique of functional programming.

Although the matrices C 2 and M S1 look the same, they are describing different aspects of the system.

We have overloaded matrix multiplication, to mean that the summation is always over the shared state in M 1 • M 2 .

Notice that the exact value y * is not important for refinement comparisons.

Def. 2 defines a pre-order on HMM 's, but it can be made into a partial order on "abstract HMM 's", introduced elsewhere[START_REF] Mciver | Abstract channels and their robust information-leakage ordering[END_REF].