Fred Cohen

TOWARD A SCIENCE OF DIGITAL FORENSIC EVIDENCE EXAMINATION

Keywords:

Digital forensic evidence examination is not a normal science at this time. This paper discusses the important issue of moving toward a science of digital forensic evidence examination. It highlights key areas in which progress has to be made in order for digital forensic evidence examination to become a normal science.

Introduction

Like almost every scientific endeavor, the examination of digital forensic evidence (DFE) started out somewhere between an art and a craft. People with special skills and knowledge leveraged their skill sets and knowledge to put forth notions about the meaning of DFE in the context of legal matters. While the court system greatly appreciates science and its role through expert testimony in providing probative information, the appreciation is substantially challenged by the lack of a scientific base. A scientific base includes a well-defined and well-understood body of knowledge, an underlying scientific methodology, an experimental basis, adequate peer-reviewed publications associated with professional societies, and all of the other things that go with normal science. As the volume and criticality of DFE has increased, there is an increasing recognition of the limitations of DFE, and more importantly, the limitations of the underlying science.

To clarify the notion of a science of DFE examination, it is instructive to examine the advancement of science in other disciplines. In most disciplines, a scientific methodology consists of four basic elements: (i) studying previous and current theories, methods and their experimen-tal basis; (ii) identifying inconsistencies between current theories and repeatable experimental outcomes; (iii) hypothesizing new theories and performing experiments to test the new theories; and (iv) publishing the results. However, in an area where there is no pre-existing scientific infrastructure, a new theory, methodology, experimental basis, and perhaps even a new physics, have to be built from scratch. In the case of DFE examination, only one such attempt has been made so far [START_REF] Cohen | Digital Forensic Evidence Examination[END_REF], and this paper is substantially about that attempt.

2.

The Call for Science in Forensics

The U.S. Supreme Court has spoken [START_REF] Supreme Court | [END_REF] and the National Research Council has concurred [START_REF]Strengthening Forensic Science in the United States: A Path Forward[END_REF]. A rigorous scientific approach is needed for forensic evidence to warrant its use in courts in the United States. Much of the world is likely to follow this approach.

To a substantial extent, this call for science stems from some dramatic failures of forensics. For example, in the Madrid bombing case, the FBI declared that a fingerprint from the scene demonstrated the presence of an Oregon attorney. However, the attorney, after having been arrested, was clearly demonstrated to have been in another part of the world during the time in question. The side effect is that fingerprints are now being challenged as valid scientific evidence around the world [START_REF] Fine | Statement of Glenn A[END_REF].

A similar situation exists in cases where forensic examiners have done poor quality work and have testified in a number of cases, typically for the prosecution. The inability to effectively challenge evidence by these supposed experts using a scientific methodology and inquiry process is extremely disconcerting, all the more so because of the limits of human integrity. In case after case, when the details are examined, forensic evidence seems to come up short under competent challenges and close scrutiny. The solution is simple. Build and apply real science, and the truth will out.

Proposing a Science

This first attempt at proposing a science for DFE examination involves the creation and enumeration of elements of an epistemology and a physics of digital information, a model of the DFE examination process in the legal environment, and the interpretation of existing information, theory, and experimental results in the new model. This is the first attempt to create a scientific model for DFE examination, and a suitable name would be "the standard model." But of course, it will only become a standard to the extent that it is embraced by the community. Also, it would have to be adapted over with time as the digital forensic community comes to decide and adapt to the realities of the scientific method.

Epistemology for Digital Forensics

Epistemology studies the nature of knowledge, its presuppositions, foundations, extent, and validity. In the case of DFE examination, some basics may be reasonably assumed for the purposes of creating a science. The following are some of the epistemological issues that have already been identified.

Digital evidence consists entirely of sequences of binary values called bits. The physics of DFE is different from that of matter and energy, and thus the normal assumptions made with respect to how the world works do not apply -or do not apply in the same way -to DFE.

Two major differences are that DFE has observation without alteration and duplication without removal. Also, computational complexity limits what can be done with resources in a given time frame -one could say that the speed of light is "different" for DFE.

Physical evidence is very often transfer evidence and is sometimes trace evidence. In contrast, DFE is always trace evidence, but essentially never transfer evidence. Also, DFE is normally latent in nature in that it can only be observed through the use of tools. This implies a multitude of requirements surrounding DFE tools and their use.

In a "scientific" approach, the theories are not casual theories, but "scientific theories." That means that: Constructs are testable.

Refutation can destroy a theory. Finite confirmations do not prove a theory; they can only confirm it. Scientific theories change slowly. Once theories are accepted, they only change -in very rare cases -because of dramatic changes in the understanding of the underlying physics.

The "theories" of DFE lead to a physics of digital information. Many of them are based on existing and widely-accepted mathematical knowledge. However, some are still conjectures from computer engineering, computer science, discrete mathematics, and related areas.

Information Physics

The physics of digital information is significantly different from that of the physical world. The differences are described in more detail elsewhere [START_REF] Cohen | Digital Forensic Evidence Examination[END_REF]. However, to get a sense of the differences, many of the under-lying assumptions of the physical world, such as smoothness, continuous space, the notion of transfer, continuous time, and even the speed of light, are very different in the digital world. Indeed, the assumptions simply do not hold and the implications are, in some sense, profound.

Input sequences to digital systems produce outputs and state changes as a function of the previous state. To the extent that the state and outputs produce stored and/or captured bit sequences, these create traces of the event sequences that caused them. Thus, a trace may be defined as a set of bit sequences produced by the execution of a finite state machine.

We generally think of the physical world as a space that diverges with time, with any given initial conditions in history producing a wide variety of possible future outcomes. As a result, when looking at a physical trace, at least theoretically, it is possible to identify a unique historical event sequence that produced such a trace. But the digital space converges with time, so instead of the one-to-many relations seen in the physical world, there are many-to-one relations in the digital world. This means that a very large number of potentially different input sequences and initial states may produce identical traces (i.e., from subsequent states and sequences). Almost any digital trace could be the result of a large number of different historical event sequences, and the number of these sequences increases dramatically with the passage of time (i.e., execution of finite state machines). Thus, the traces from digital devices are not, in general, unique as to the input sequences that produced them.

Another less mathematical problem is the relationship between the unlimited granularity of the physical world in time and space and the finite granularity of the digital world in time and space. Because of this difference, a discontinuity exists at the interface between the physical and digital world. Minor differences are exaggerated near the discontinuity while major differences are ignored away from the discontinuity. The limited sensor and actuator capacity of devices that convert between the digital and physical world prevents the exchange of a variety of information that is potentially probative, and makes it much easier to create a variety of forgeries at the interface. This implies that input sequences may not directly demonstrate which non-digital events sequences may have produced them. As a result, additional effort is required to attribute traces to real-world causes and forgery is much easier in the digital space than in the physical space.

Viewing DFE as the result of processing by finite state machines inherently limits the potential utility of DFE examination for providing probative information about real-world events. DFE examiners must take the limitations into account when performing their examinations and when testifying about the results of the examinations. These limitations are directly due to the limits of DFE and the methodologies used to understand and work with it.

DFE Examination Model

The model of DFE examination is related to an overarching model of digital forensics [START_REF] Cohen | Two models of digital forensics examination[END_REF]. It can be codified in mathematical terms as follows:

Laws: L : {l 1 , . . . , l n }, R : {r 1 , . . . , r m }, L × R → [F |T ] Violations: L × R ⇒ V Claims: E : [{E 1 , . . . , E o }] Events: ∀e, e ∈ E * that demonstrate claims [∀Ex ∈ E, Ex : (ex 1 ∈ E * , . . . , ex p ∈ E * )] Traces: T : (t 1 , . . . , t q ) Internal Consistency: C : T × T → [-1, 1] Demonstration Consistency: D : T × E * → [-1, 1] Forensic Procedures: P : {p 1 , . . . , p n }, ∀p ∈ P, p → c ⊂ C, p → d ⊂ D, p → c ̸ ⊂ C, p → d ̸ ⊂ D Resources: R : (T, $, C, E)
Schedule Sequence: S : (s1, s2, ...), ∀s ∈ S, s :

(l ⊂ L, r ⊂ R, h ⊂ H, e ⊂ E, t ⊂ T, c ⊂ C, d ⊂ D, p ⊂ P, r ⊂ R, t, t ′ )
In essence, the legal claims constitute a set of runs through the elements of laws that produce violations. This can be conceptualized as a partially-ordered set (poset). The events and traces are entities that are evaluated to determine the outcome of the legal matter, and they form the basis for the claims that are demonstrated using the violation poset. If the events and traces are consistent with an unbroken path through the poset, a violation is indicated; if not, inadequate indications for a violation are present. If T and E are inconsistent with the poset, then they may act to sever all of the paths forming violations, in which case adequate basis may be present to definitively demonstrate that no such violation is justified. To the extent that T and E are internally or demonstrably inconsistent, C and D may be used to show that the evidence or the claims are less probative, or potentially even prevent the admission of elements of T and/or E into the matter.

The fundamental theorem of DFE examination in this model may be stated in relatively simple terms:

What is not consistent is not true. DFE examination then consists largely of testing hypotheses related to the poset that form V as demonstrated by T and E in order to attempt to refute them by showing that they produce inconsistencies. This also implies some things about language and usage.

Consistency and inconsistency are demonstrated by logic and the theories associated with the physics of digital information. So, for example, given that a claim is based on an event e 1 causing a trace t 1 , events and/or traces showing that t 1 happened before e 1 would be inconsistent with the claim of causality because information physics demands that cause precedes effect.

There are several consequences of this model related to: (i) the sizes of the model components; (ii) available computing power and its impact on thoroughness; (iii) limitations due to resources and schedules; (iv) limitations of available procedures; (v) legal limitations on what can be used and how; and (vi) probative versus prejudicial value and its relationship to consistency and related matters. In the example above, refutation is based on traces and events that may themselves be problematic. Thus, C and D are defined over the range [-1, 1].

In many cases, because of the limitations of DFE examinations as described here and elsewhere, more certainty is desired. Two general classes of methods exist to provide higher surety of DFE examination results: (i) identifying additional traces or procedures to gain additional demonstrations of consistency or inconsistency; and (ii) identifying redundant paths to prove hypotheses so that even if some paths are less certain or are eliminated, the overall hypotheses remain intact. These issues are covered by the model presented here.

Use of Defined Terms

No matter how many tests are performed, except for special cases, DFE examination results cannot prove a broad claim to be true [START_REF] Popper | The Logic of Scientific Discovery[END_REF]. The best that can be done is to show that the tests undertaken fail to refute the hypotheses and to show the extent to which the tests were thorough. This leads to the notion of what can reasonably be asserted as the most authoritative claim in [opposition] support of a hypothesis regarding DFE:

"The results of {the tests I did} were [in]consistent with {the hypotheses}."

To the extent that some of these statements are combined by logical reasoning, an overarching statement may be made with regard to the claims. This could be of the form: "Based on {the basis}, the {traces and events} are [in]consistent with {identify the claim(s)}." Or in some cases, when this is true:

"In my examinations of {traces and events}, everything I found was consistent with {claims} and nothing I found was inconsistent with {claims}." On the other hand, a single refutation disproves a hypothesis. The least that can be reasonably said if such a refutation is identified is:

"The {procedures I performed} demonstrate that {traces and events} are [inconsistent with/refute] {the hypothesis}." Thus, the methodology underlying the science of DFE involves:

Devising testable hypotheses (E)

Testing the hypotheses against the evidence (T and E) using forensic procedures (P ) and logic to determine Type C and D consistency by attempting to refute the hypotheses.

Making careful and limited statements about the results of these tests, typically using wording such as that identified above.

The following are some wordings that may apply in other circumstances. Some of the more commonly misused ones are also identified, along with definitions appropriate for use by DFE examiners.

Suggest: Imply as a possibility ("The evidence suggests ...")calls to mind -propose a hypothesis or possible explanation.

Indicate: A summary of a statement or statements or other content codified ("His statement indicates that ...") -a defined set of "indicators" are present and have, through some predefined methodology, and identified as such ("The presence of [...] smoke indicates ...").

Demonstrate: Exemplify -show -establish the validity ofprovide evidence for ("The reconstruction demonstrates that ...

").

Correlate: A statistical relation between two or more variables such that systematic changes in the value of one variable are accompanied by systematic changes in the other as shown by statistical studies ("Based on this statistical analysis, the use of the KKJ account is correlated (p=95%) with ...").

Match: An exact duplicate ("These two documents have matching publication dates, page counts, ...").

Similar: A correspondence or resemblance as defined by specified and measured quantities or qualities ("The 28 files were similar in that they all had syntax consistent with HTML, sizes under 1,000 bytes, ...").

Relate: A defined and specified link ("The file system is related to FAT32 in that FAT32 was derived from ...").

Associate: Make a logical or causal connection with basis provided ("I associate these bit sequences with program crashes because ...").

Through the careful use and consistent application of these terms, the field of DFE examination may move forward more quickly, and peer reviews could create a body of work that is meaningful across endeavors and time. However, if, the DFE community is inconsistent or if its peer review process fails to force compliance with the terminology, then DFE examination is unlikely to proceed as a normal science.

Tools of the Trade

As an area of science, DFE examination has a relatively small number of peer-reviewed and repeatable scientific experiments. Most experiments are of limited applicability and are not focused on building a fundamental understanding. They do not meet the standards of scientific rigor expected in other fields. They are oriented toward confirmation rather than refutation, which makes them dubious as science.

Furthermore, there is a methodological challenge associated with experiments for several reasons. DFE is latent and, therefore, experiments require tools. Of course, this means that the experiments are limited by the tools and, like any other area of science, the examiner must understand the limits of the tools in order to understand the limits of the experiments. This, in turn, leads to the need to have a methodology to evaluate tools. Without such a methodology, regardless of what the tools may indicate, the interpretation of the results is open to question.

A methodology for understanding tools might start with the development of an error model. Classical error models for digital systems [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF][START_REF] Breuer | Diagnosis and Reliable Design of Digital Systems[END_REF] may well be applicable, but their utility will not be known until they are applied in DFE examinations.

It is also important to understand how to calibrate and test tools, and to create systematic approaches for doing so. Calibration processes typically involve validation with known samples, which is readily done in most cases. The testing process typically involves verification of some sort, which, in the case of software, normally involves mathematical proofs or tests that verify the results against error models. Again, this is an area where DFE examination is lacking. Redundancy via the independent verification of results may provide an alternative in cases where no well-defined testing methodologies and practices are available.

Regardless of how "good" a tool is, it must be properly used, the results must be meaningfully interpreted, and the limits of the tool must be understood. This implies that the examiner must have knowledge, skills, education, training, and experience suited to the use of the tools they apply. DFE examination has few advanced students and teachers and, as a result, produces "niche experts," who are of limited utility. It has many niche experts who can potentially speak to very narrow domains and it has expert claimants who profess expertise beyond their actual knowledge, skills, education, training, and experience. Indeed, DFE examination as a field has too few "real experts" at this time.

Presentation

Another major issue with tools today is how they present results, both in support of the examination process and when the results of examinations are presented in reports or before judges and juries.

Presentation is intimately tied to, but not directly part of, examination. Because DFE is latent, presentation will always be an issue. For the examiner, the results of the experiments must be presented using tools. For the jury, presentation is again fundamental to understanding the evidence and the examination results. For the judge, the same is true to evaluate admissibility. For the opposition, presentation is just as critical to evaluating expert reports,. Today, however, there is no standard for even presenting the most common representations of DFE. Even something as simple as presenting a text file is fraught with potential errors.

Different ways of presenting the same information can lead to different interpretations and outcomes. Consider this simple example: Plaintiff's sworn statements are inconsistent with the evidence. If Plaintiff's sworn statements are to be believed, then the evidence refutes Plaintiff's claims.

If the evidence is to be taken at face value, then it refutes Plaintiff's sworn statements.

The first of these statements encompasses the other two. The second statement appears to say that one can assume that the plaintiff is telling the truth, but the evidence does not support the claim. The third statement appears to say that the plaintiff is lying.

Technical presentation errors are also problematic. For example, the digit "O" and the letter "0" are almost indistinguishable, as are the digit "l" and the letter "1." Spaces at the ends of lines, and the differences between a leading tab, a leading space followed by a tab, and leading spaces cannot be discerned in normal printouts. As an aside, the nature of the problem becomes very clear if the reader failed to notice that the numbers "0" and "1" and the letters "O" and "l" are interchanged above.

When examining the output from widely-used and trusted tools, the presentation produced by the tools often fails to aid the examiner in seeing these sorts of differences. In case after case and in tool after tool, differences that might allow the examiner to detect inconsistencies go unseen and, thus, the inconsistencies are commonly missed. Even something as simple as a forensic font would largely alleviate these problems, but this notion was only first introduced in late 2009.

Clearly, presentation is fundamental to the advancement of a science of DFE examination. Also, presentation is critical to the effective use of tools upon which essentially all of digital forensics depends.

State of the Science

The principal elements of DFE examination are analysis, interpretation, attribution and reconstruction. While this categorization of the discipline may be somewhat arbitrary, it is sensible in that each of these elements, while not entirely distinct from one another, encompasses different techniques that may require different expertise and tools.

Analysis

Analysis engages techniques that provide definitive answers to specific questions. Existing analytical techniques are limited in number and in the nature of the definitive results they produce. The techniques are computational in nature with defined complexity and defined input and output limitations, and their accuracy can be verified (at least theoretically). Methods that do not meet these criteria should not be called analysis.

Analysis starts with a bag of bits. Redundancy in the bag of bits confirms or refutes hypotheses about what the bag of bits is. Through analysis, features and characteristics are detected, symbol sets are iden-tified, trace typing is undertaken, content is parsed, normalized and elucidated, and indicators are analyzed. Any of these may return the examiner to a bag of bits, especially if it produces inconsistencies that destroy the chain of analytical results supporting the current hypotheses about the bag of bits.

During analysis, characteristics and features are analyzed for consistency, traces are ordered and out-of-order entries are detected, sourcing and travel patterns are identified, consistency is checked across related records, anchor events are used for external validation, time differentials and jitter are considered, and all of these are compared with hypotheses in order to identify consistency or inconsistency. Also, sieves are constructed and items are counted, derived traces are formed for analytical convenience, counts are made of various features and characteristics of interest to the examiner, mechanisms are combined and the resulting errors identified and mitigated, and results are verified by independent means where feasible. Additionally, intentionally-hidden items of interest are sought, content placed in hard-to-find locations is found, steganographic and other transformed content are identified and inverted, recursive embedded languages are parsed, and indicators are identified and sought relative to the issues at hand.

In these analytical processes, automated and human cognitive methods are combined to identify potential Type C and D consistencies and inconsistencies either automatically or through DFE examiner interaction. All of these processes are limited by the available forensic procedures (P ) and their computational complexity, which impacts and is impacted by resources.

Interpretation

Traces, events, claims, and analytical results must be interpreted in the context of the legal matter in order to be meaningfully examined. Interpretation involves selecting among alternative explanations (hypotheses). Different interpretation methods are used for different circumstances, with one major difference being the treatment of structured and unstructured traces.

Over-interpretation by examiners is common. For example, terminology is misused, conclusions are drawn in excess of what is supported by the data, the terms "match" and "correlate" are overused, and the details of the basis are often left unspecified.

Special care must be taken in making statistical claims. In addition to simple interpretation errors (e.g., percentages that add up to more than 100%), claims often ignore data that is not present, conceal assumptions related to random stochastic processes and other similar things, and assert precision exceeding accuracy. This is particularly problematic in digital systems, where 33.333% results from an experiment with only 9 samples. At best, there is a little less than one digit of accuracy, so this precision is misleading. The examiner must interpret the output of analyses and present information in clear terms in order to properly interpret results for presentation -3 of 9, 1/3 or 33% are all valid, but 33.333% is not.

Tools commonly interpret traces as well, and to the extent that they do so, these interpretations make assumptions, often without basis. The interpretations often present false results based on the assumptions and result in presentations and other depictions that may mislead the examiner as well as the judge and jury. No methodology currently exists for evaluating interpretation by tools, although a wide range of cognitive errors are known to cause incorrect or imprecise interpretation.

Interpretation includes the identification and explanation of missing traces and their implications to the matter at hand. While some experts may know the traces that are commonly present in some situations, there is neither a widely available library of what constitutes "normal" behavior in an operating environment nor a basis for comparison in the existing literature.

While redundancy may be used to mitigate interpretation errors, interpretation is highly subject to individual variations. Proper interpretation is limited and couched in terms of its accuracy and applicability, including the things that the examiner does not know. It is important to enforce careful word usage for technical terms in professional publications and in legal venues. How can one claim to be an expert when one does not even use the published and accepted terms of the scientific and technical community?

There is also a tendency to create casual theories and embrace them as if they were something more. To be clear, the theories of DFE examination are the results from information physics, the assumptions of the model, and the foundational logic and results of computer science and engineering. Any other theory, unless and until it passes peer review and is reconciled with the existing theory, is only a hypothesis at best.

Examiners, like all people, make cognitive errors during the interpretation process. The examiner would be well served to examine the literature in this area and apply it to maintain clarity regarding his/her own as well as others' potential for making mistakes. Indeed, it is unwise to believe what one thinks is right unless one really knows. What some reviewers call "put a stake in the ground" should be shunned in the DFE community in favor of properly identifying the limitations and not overstating a case. Peer review of examination results, particularly interpretations, should be sought in every case and for every report.

As a working assumption, the DFE examiner should assume that each system and situation is in fact different from others. Experience is a great teacher, but it can be misleading. Care must be exercised in not over-interpreting the data. And when the interpretation is unclear, reconstruction is a viable and worthwhile approach for gaining additional data. All interpretation should also be made within the context of information physics, and with the working assumption that every interpretation will be tested against information physics and refuted if it is inconsistent.

Events are also subject to interpretation because words are interpreted by examiners. Cognitive errors in interpretation are common and, since examiners assume the context of their knowledge and words mean different things to different people, the careful interpretation and close scrutiny undertaken by an examiner may be viewed as being "picky" by others; but this is the nature of interpretation in the legal environment. Furthermore, events are often difficult to interpret and leave many possible interpretations, particularly in light of the lack of specific technical knowledge by the individuals who offer the information related to the events.

Events should presumably be viewed through the lens of information physics. Claims are often inconsistent with and are, thus, refuted by the careful use of physics. As an example, causality is tricky because of the requirement for time ordering and the fact that complexity limits actions in the digital space; this results in a poset of causal relationships. Reviewing information physics for events may be helpful, but being thorough in this regard is problematic because of resource limitations and the lack of apparent progress when the examiner is thinking about the issues in light of other considerations. At this time, it is not possible to automate much of this examination and most DFE examiners lack the time or knowledge to do a thorough (or even thoughtful review) against the full set of theories.

Resources limit interpretation and tight schedules may prohibit contemplation of the issues in many cases. Computational resources and costs may be prohibitive for certain procedures, especially when a large volume of traces are involved. Available traces may change with time and legal actions as well.

Statements made and documents created by examiners are often unnecessarily interpretive. Careful wording is highly desirable in written and verbal communications. There are few "standard wordings" for DFE examination, and examiners often make statements that end up being wrong, but that could have been accurate had they been stated differently. For example:

"I found X B's in File Q" is true even if there are more than X B's present, because, presumably, the examiner did not find the other ones. On the other hand, the interpretation:

"There were X B's in File Q" is potentially problematic given the same circumstance. It is a good idea to minimize interpretation and favor statements of fact wherever possible.

Similarity is almost always interpretive, in large part because DFE examination lacks adequate similarity metrics or criteria, an experimental basis for many similarity claims, and techniques for detecting similarity in many cases. Still, examiners have the tendency to use the term "similar" when it cannot be backed up with facts. Similar problems are often indicated and commonly associated with the suggestion of matches relating associated correlations. Clearly these uses are unclear and imprecise, and the lack of clarity and precision during use, while perhaps suggestive to the untrained reader, should be readily identified as indicative of a lack of knowledge, education, and training in DFE examination.

Assumptions underlying interpretations are critical, but they are often not detailed in statements and reports. Thus, the statements and reports lack the basis for the interpretations. It may be hard to identify all the assumptions, but confirming/refuting assumptions and hypotheses is the process that should be relied upon in interpretation; therefore, identifying and presenting them is important to obtaining the right answer.

Presentation is also an interpretive function that drives every aspect of DFE examination. It acts within the process of examination to skew the approaches and procedures used by the examiner. The presentation provided by a tool is the only thing the examiner has to rely on to understand the latent traces. Examiners must understand that they are interpreting the output of tools and that the outputs and interpretations are fraught with the potential (often realized) for producing cognitive faults, leading to failures that may significantly impact examination results and process.

Attribution

Correlation is not causality; before is not because. On the other hand, a lack of correlation certainly throws considerable doubt on the notion of causality, and the cause had better be before the effect.

Attribution of actions to actors is centered on the notion of causality, to the point where they are, in essence, inseparable. The fundamental assumption of causation in the digital world is:

Traces come about by the execution of finite state automata that follow the physics of the digital world.

The physics of the digital world is useful in assessing attribution claims. For example, A caused B implies that A came before B. How long before is determined by the digital version of the speed of light. Computational complexity, the performance levels of devices, the physical speeds associated with the devices and their components, and the mechanisms available for storage, transport and processing, all place limits on the interval of time between the cause and the effect.

Statistics do not apply in most cases relating to attribution because the past is what it is; there is no "might have been" or likelihood that some particular thing happened. Either it happened or it did not happen.

Establishing a causal chain is non-trivial as well. It often involves redundant records and almost never eliminates all other possibilities. But it may provide a seemingly overwhelming body of information that is consistent with the hypothesis of attribution, and no information available may lead to inconsistencies with a hypothesis. This becomes a compelling argument for a judge or jury, even if the examiner never claims it to be definitive.

Finite state machines are highly predictable because driving state and input to output leads to the same answer every time in almost all cases. However, finite state machines converge with time (while the real world diverges), so where simulation may produce identical outputs, reversing time does not give a unique answer. Therefore, in the digital world, convergence implies that many paths lead to the same traces. In addition, because sensors that change physical inputs to digital outputs are highly nonlinear, small differences are expanded near a nonlinearity while large differences are reduced far from a nonlinearity. Thus, the interface tends to break the digital perfection of even forward-driven causal chains.

Attributing actions to human actors is even more problematic. Authentication methods are of limited value. Most biometrics are not good for identification, but rather only for selecting a known individual out of a group of a few thousand known individuals when deception is not in use. Something the user has can be taken or exploited; something the user knows can be known by others; something the user can do can be done by others. DFE can almost never put a person at a keyboard at a time, although other events may be able to help. And even if the user is at the keyboard, it does not necessarily mean that he/she was in control of the computer. Behavioral attribution may use words and word sequences, commands that are executed and usage patterns, keyboard use and timing patterns, etc., but all of these fail under deception. Also, they are limited to picking known individuals out of small known groups and they have significant error rates even under non-stringent test conditions.

Device authentication and attribution may be accomplished using various indicators (e.g., operating environment identification data, device identifiers, and known behaviors of programs and mechanisms). While most of these are readily subverted by deception, some have properties that make them difficult to forge. Redundant traces may be applied to reduce the impact of deception.

Attribution of damage to parties is also important, e.g., to establish threshold requirements for criminal charges. Actual damages are typically divided into: (i) physical damage; (ii) conversion to use by another party; (iii) deprivation of utility to the owner, which is often the key DFE issue; and (iv) lost value or lost rights (e.g., disclosure of trade secrets or release of pre-patent data). If attribution can be done of the cause to effect, computation methods are available to identify the extent of the deprivation. This may include things such as the cost per usage of electricity, cost in reduced lifetime of equipment, cost in demonstrable lost business, and cost in reduced life of equipment.

Reconstruction

Driving time backwards is one approach to reconstruction, but information physics shows that this is problematic. The lack of adequate traces over time leads to very large envelopes of possible histories, which make it almost impossible to tell what was "original." In addition, theft may not be identifiable, travel time and jitter produce ordering uncertainties, and reversing time in a unique manner through homing sequences is impossible. Error accumulation also leads to large expansions when reversing time. The list goes on and on, which leads to the alternative of experimental demonstration of operation in the forward direction.

Experimental demonstration of operation in the forward direction is a form of reconstruction that can be used to test hypotheses. As such, it can confirm, refute, or be unrevealing. The basic methodology deals with constructed traces (C-traces) and original traces (O-traces). Similarity measures are used to define, in advance, the criteria for identifying sets of C-traces mapped to O-traces, and the implications of outcome class sets. The examiner creates reconstruction(s) based on hypotheses, generates C-traces, and compares the C-traces to the O-traces to confirm or refute hypotheses.

5.

Toward a Normal Science

Based on the discussion above, the following statements can be made today based on the science of DFE examination: "I did X and observed Y." "I [did not find/found] X in Y." "X is [in]consistent with the claim Y because..." "X [suggests/indicates/demonstrates/correlates with/matches/is similar to/relates to/associates with] Y because..."

If examinations are properly undertaken, each of these can have a sound basis with the proper scientific underpinnings. Unfortunately, the current set of methodologies, processes and procedures are limited in terms of their validity, testability, reliability, calibration, and basis. Additionally, there is a lack of strong agreement within the DFE community about many aspects of the science as a whole. While most of the results are peer reviewed and accepted within individual communities, several problems exist:

The overall collection of results (as a body of science) is not recognized as such.

The unifying methodology expressed with regard to the application of information physics to determine consistency is gaining acceptance very slowly.

Models that are currently in use are used for various limited purposes, and are not widely adopted.

Procedures and their results are limited and are not formalized or standardized.

Tools and processes are only explored to a limited extent, with notions of completeness and thoroughness just beginning to be defined.

Error models have not been adequately applied from other mature fields. The sources and magnitudes of uncertainty are poorly defined, and confidence intervals simply do not exist.

In most cases, the honest and knowledgeable examiner is largely limited to the most basic: "I did X and observed Y," with the observation being typically limited to: "I [did not find/found] X in Y."

While these are powerful statements that are appropriately used in place of other less sound statements, they are a long way from the level of science that DFE examination has the potential to achieve.

Conclusions

DFE examination is not operating as "normal science" today. While there is a scientific basis for many activities involved in DFE examinations, a widespread consensus and common methodologies are still lacking. The foundation for scientific theories exists, but little attention is paid to testing the theories and developing the science. To successfully make the transition to a normal science, the DFE community will have to ask and answer several questions: What well-defined and consistent terms should be used?

What well-understood epistemology should be used? What theories and methodologies should be chosen? What strong experimental foundations should be built?

What agreed-upon physics should be used and how should it be formulated?

How could community consensus be built? Should the path outlined here be embraced?

If not, what is the best path?

The view of this paper is that there exists at least one description of a reasonably comprehensive scientific foundation underlying DFE examination. Regardless of the problems and limits of the foundation, it is a place to start building a normal science and advancing the field. As the field matures, normal science is almost inevitable, but the normalization process is only just beginning. A community consensus is highly desired, and this paper supports and anticipates such consensus in the near future.


Bradley Schatz

Michael Cohen

REFINING EVIDENCE CONTAINERS FOR PROVENANCE AND ACCURATE DATA REPRESENTATION

Keywords: Evidence containers, representation, provenance, tool interoperability

It is well acknowledged that there is a pressing need for a general solution to the problem of storing digital evidence, both in terms of copied bitstream images and general information that describes the images and context surrounding a case. In a prior paper, we introduced the AFF4 evidence container format, focusing on the description of an efficient, layered bitstream storage architecture, a general approach to representing arbitrary information, and a compositional approach to managing and sharing evidence. This paper describes refinements to the representation schemes embodied in AFF4 that address the accurate representation of discontiguous data and the description of the provenance of data and information.

Introduction

One of the principal challenges in digital forensics is to deal with the rapidly growing volume and complexity of information that is the subject of investigations [START_REF] Carrier | Defining digital forensic examination and analysis tools using abstraction layers[END_REF]. The acquisition and analysis of digital evidence are hampered by the lack of interoperability between forensic analysis tools; important forensic information is often unused by analysis tools because it is locked within proprietary file formats or free text. Access to case data is hampered by closed abstraction layers and the inefficiencies imposed by the need to manually copy data in order to process it with task-specific tools. Finally, the management of evidence is slowed by format conversion and storage bandwidth limitations.

Digital forensic practitioners have largely settled on the raw (dd) and Expert Witness Format (EWF) evidence storage formats for hard drive images. This has enhanced the ability -in the storage forensics field at least -to acquire and analyze evidence using a variety of tools of commercial and open source lineage.

Such formats are, however, poor surrogates for the original evidence. A raw image fails to distinguish between sectors containing bytes with the value zero and those where a read error has occurred. A raw image does not record provenance-related information pertaining to the drive such as the drive geometry and drive configuration overlays, nor does it record the activities performed on the drive or image. The EWF format popularized by the EnCase tool is similarly limited; however, it does overcome some of the weaknesses of a raw image by recording limited meta information related to the image within the container itself.

In practice, provenance information describing the evidence and its outside context rarely becomes grist for the automated forensic mill, mainly because it is collected and recorded manually by investigators in a variety of formats, including handwritten free text and ad hoc file formats. New approaches are required to represent digital evidence, both in terms of raw bits and bytes on storage media (data) and information describing related artifacts, entities and analytic results.

In an earlier paper [START_REF] Cohen | Extending the Advanced Forensic Format to accommodate multiple data sources, logical evidence, arbitrary information and forensic workflow[END_REF], we introduced the AFF4 evidence container format, which is designed to store arbitrary evidence images, contextrelated information and analysis results within a unified container format. This paper describes refinements to AFF4 that address the accurate representation of discontiguous data and describe the provenance of data and information.

Ideal Evidence Container

The ideal evidence container would present to the investigator a perfect surrogate of the original physical evidence, whether it is a hard drive, mobile phone flash memory or computer RAM. Such a container would fully describe the characteristics, behavior, content and context of the original evidence that it represents. These include: Data Content: Multiple streams (HPA, DCO); hierarchical data relationships (logical imaging); addressing windows (RAM holes, bad sectors); addressing schemes (block size, CHS/LBA); SMART status. Physical Characteristics: Make; model; serial number; interface (SATA, SCSI, etc.).

Context: Environment in which the hard drive existed; caserelated information.

Behavior: Error codes related to bad sectors.

A perfect fidelity surrogate -even if it were technically feasible -would not be entirely desirable. Such a "virtual hard disk" would quickly frustrate the investigator by reliably imposing characteristics such as read retries on bad sectors, I/O bandwidth limitations and seek latency. Accordingly, the ideal container would sacrifice fidelity to satisfy orthogonal operational concerns such as:

Efficiency: Storage space minimization; random access performance; I/O speed.

Authentication: Cryptographic signing; hash storage. Privacy: Encryption; redaction.

Resilience: Tolerance to underlying storage media failures.

Current State of Evidence Containers

From the original raw evidence format, evidence containers evolved to incorporate seekable compression [START_REF] Cohen | Extending the Advanced Forensic Format to accommodate multiple data sources, logical evidence, arbitrary information and forensic workflow[END_REF], embedded authentication and integrity mechanisms such as hashes and CRC, and storage of a small number of fields for describing images. More recently, the demand for logical imaging has resulted in the emergence of a proprietary evidence container format that supports the storage of multiple streams of data along with file-oriented metadata (EnCase Logical Evidence File).

This current breed of commercial evidence containers does not address the characteristics of evidence sources. For example, hard drives may contain multiple address spaces, depending on whether features such as host protected areas or drive configuration overlay are enabled. Images of computer RAM require the consideration of holes in which no data exists. Furthermore, the evidence containers fail to address the storage of general information that is of relevance.

The research community has proposed a number of container formats. The Advanced Forensics Format (AFF) [START_REF] Garfinkel | Providing cryptographic security and evidentiary chain-of-custody with the Advanced Forensic Format, library and tools[END_REF][START_REF] Malan | Advanced Forensic Format: An open, extensible format for disk imaging[END_REF] introduced the storage of arbitrary metadata within an evidence container, privacy via encryption and redaction, and resilience via fault tolerance. Digital evidence bags [START_REF] Turner | Unification of digital evidence from disparate sources (digital evidence bags)[END_REF] store arbitrary textual information along with images in the same container. Sealed digital evidence bags [START_REF] Schatz | An information architecture for digital evidence integration[END_REF] employ a composition framework for evidence containers based on a linked information model.

We recently introduced the AFF4 evidence container format [START_REF] Cohen | Extending the Advanced Forensic Format to accommodate multiple data sources, logical evidence, arbitrary information and forensic workflow[END_REF], which defines an efficient, seekable, compressed storage format for multiple data object images, a novel and powerful data model that enables the composition of data objects from other data objects, and an information

N N N N ? N N Y Data Composition N N N N N N N Y Seekable Compres- sion N Y Y ? N N Y Y Information Representation raw EWF sgzip LE1 DEB SDEB AFF1 AFF4 Metadata Storage N Y N Y Y Y Y Y Arbitrary Metadata Storage N N N ? Y Y Y Y Arbitrary Informa- tion Storage N N N N Y Y N Y Formal Information Model N N N N N Y N Y Composable Infor- mation Model N N N N N Y N Y
representation approach based on a linked information model. Table 1 compares the characteristics of AFF4 and those of other evidence container formats.

AFF4 Data and Information Models

The general design goals of AFF4 are to provide an open and extensible evidence container that facilitates the storage, composition and sharing of arbitrary types of digital evidence, information and analysis results. AFF4 defines two interrelated models, one for representing and documenting information, and the other for storing, referring to and transforming bitstream data. The two models are linked by a naming scheme in which items of relevance are identified using globally-unique identifiers. The AFF4 data model is specifically designed to facilitate the storing, sharing and referencing of data without imposing the storage bandwidth burden of copying data, while providing efficiency in terms of storage space, random access latency and I/O bandwidth. Likewise, the AFF4 information model is designed to facilitate the description of forensically-relevant information, including evidence, case context and general analytic results.

The "by reference" approach of the AFF4 architecture facilitates the successive layered application of discrete task-specific tools on the analytic results and data abstractions of tools operating at lower layers of abstraction. In the architecture, the analysis results of a tool are persistent when using the AFF4 information and data models in a new AFF4 container or in an existing container. This significantly differs from other approaches that either keep analysis results as intermediary structures in the working memory of a tool (as in monolithic applications like EnCase) or dump the results to an ad hoc (and likely non-machinereadable) document.

Figure 1 presents the flow of information and data between AFF4aware forensic applications and AFF4 evidence containers. In this example, an examiner employs an AFF4 imaging application to create two disk images in a single container. Each image has two virtual address spaces overlaying it: one for the regular portion of the disk and the other that includes the HPA portion of the disk. The examiner uses the GUI of the tool to enter case-relevant and context-related information associated with the images; meanwhile, the imaging tool records provenancerelated information obtained directly from the drives. Finally, the tool records the MD5 hash of the entire disk and the information related to media failures.

Upon returning to the laboratory, the examiner proceeds to preserve the evidence. A piecewise hash of the disk is created using SHA-256 or some other hash algorithm (this is performed in the laboratory because a hash algorithm such as SHA-256 is too slow to use in the field). The computed hash values are stored in a new container, which refers to the original container.

The investigator then uses a public key to cryptographically sign the information associated with the image, including the piecewise hashes. This signature is stored in the new container.

Automated processing of the image may involve a filesystem interpreter to create virtual file instances for each file in the image, instances for deleted files and instances for unallocated space. These are also placed in a new evidence container for subsequent consumption by other tools. The unallocated space is then processed by a file carver, the results of which are stored as virtual file instances in a new evidence container, resulting in zero copy file carving [START_REF] Meijer | The Carve Path Zero Storage Library and Filesystem[END_REF].

This scenario demonstrates the feasibility of the AFF4 architecture with respect to forensic imaging, piecewise hashing, signing and using filesystem interpreter applications.

AFF4 Naming Scheme

The fundamental premise of representing both data and information within AFF4 is that an object instance is created for any virtual or realworld entity -be it a disk partition or a suspect. The object instance acts as a surrogate for the real or virtual entity. Surrogates are identified by associating a globally-unique identifier with each entity. We use both uniform resource locators (URLs) and uniform resource names (URNs) as entity identifiers.

We define structured URNs, which we call AFF4 URNs, for identifying surrogates. An AFF4 URN is made globally unique by including a GUID in its form:

urn:aff4:195bdf58-1bc9-4ba4-9a9c-f1c312673fbf
We use a variant of the ZIP file format for a default container. Thus, an investigator who visually examines an AFF4 volume containing a disk image would readily identify AFF4 URNs in the following locations:

The information segment, which is a file in an AFF4 container, contains a serialization of all the objects within the volume. The base attribute of the RDF serialization refers to the volume URN.

Image file segments are present in a folder within the ZIP file, where the folder name is a filesystem-friendly encoding of the URN that uniquely identifies the image. For example, a folder named urn%3Aaff4%3A195bdf58-1bc9-4ba4-9a9c-f1c312673fbf might refer to the image stream urn:aff4:195bdf58-1bc9-4ba4-9a9c-f1c312673fbf/. Archive filenames can be shortened relative to the volume URI. For example, the folder diskimage corresponds to the fully-qualified URI urn:aff4:volume URI/diskimage.

Information segments (described in the next section) contain URNs within their text.

URLs, which are typically used to uniquely identify a piece of terminology, may be found as text within information segments and maps. For example, we use the following URL to represent the concept of an "Image:" http://afflib.org/2009/aff4#Image

6.

Refining the AFF4 Information Model

The original AFF4 information model was inspired by the Resource Description Framework (RDF) [START_REF]World Wide Web Consortium, RDF/XML Syntax Specification (Revised)[END_REF], the data model that underlies the Rich Site Summary (RSS) feeds used by blogging software. The RDF data model facilitates object-oriented modeling with the key difference that objects in the RDF universe have unique names and properties, and the attributes and relationships of individual objects may be published in different documents.

While the original information model is intuitive and simple to implement, it suffers from several shortcomings:

The method of mapping the information model to container segments (i.e., serialization scheme) results in inefficient storage when large numbers of information instances are described.

The information model is not expressive enough to describe provenance-related information.

The AFF4 serialization scheme is verbose, which makes it difficult to read.

The lack of value types leads to ambiguity in interpreting values. Also, there is no syntactic means for distinguishing between values and URI references.

For these reasons and for standardization and interoperability, we abandon the ad hoc RDF variant and instead adopt RDF in its entirety as the information model. Under the new scheme, information is stored in information segments whose suffixes represent the RDF encodings.

For example, the name information.turtle in the AFF4 container, refers to an RDF serialization using the Turtle encoding scheme [START_REF] Beckett | Turtle: Terse RDF Tripe Language, World Wide Web Consortium[END_REF]. For conciseness and readability, we use Turtle as the default RDF serialization syntax. The URN of the serialization component is significant, with the path component being interpreted as the graph name in which the encoded RDF exists.

Provenance of Information

This section describes a general approach for expressing the provenance of statements in the AFF4 universe. Provenance statements are required to express information such as which tool generated which image or analysis products, and to sign statements.

The original AFF4 provides for provenance-related statements in the particular case of signing. However, the identity object, which implements signatures, presents some difficulties in the case of provenance statements:

The semantics of the statement file in relation to its enclosing instance is inconsistent with the information model.

Statements within a statement file are also made elsewhere within the container.

Verifying the signatures of statements requires that the statements be in the exact order and syntax in which they exist in the signature file.

A general solution to provenance requires a method for referring to a set of RDF statements as a whole. Such statements about statements are called "reified statements" in the knowledge representation literature. A simple example is: Dick said "The serial number of the hard drive is ZX322o91 and its hash value is 13343af423d."

The subject Dick is making a statement covering two separate statements: "The serial number of the hard drive is zx322o91" and "The hash value of the hard drive is 13343af423d."

A widely acknowledged problem of RDF is its limited ability to express reified statements [START_REF] Carroll | TriX: RDF Triples in XML[END_REF]. Named graphs constitute a solution to the problem of reification in RDF, with the TriG language emerging as a syntax for encoding reified information [START_REF] Carroll | Named graphs, provenance and trust[END_REF]. A named graph is simply a collection of RDF statements that can be identified by an unambiguous name. Using the TriG syntax, the reified statement above can be expressed as:

1 @prefix G1: <urn:aff4:19857a87-a190b2f87> 2 @prefix Hdd1: <urn:aff4:652e4027-27fab2941> In the listing above, Lines 1-4 define namespace identifiers that are substituted when they occur elsewhere in the document. For example, in Line 7, aff4:serialNumber is interpreted to mean the URL http://afflib.org/2009/aff4#serialNumber. This uniquely-identified vocabulary term is defined to have the meaning of a serial number. In Lines 6-9, G1: is the unique identifier for the named graph that contains the two statements referred to in our example. Named graph identifiers may be referred to in the subject and object parts of RDF statements. Finally, in Line 11, there is a single statement that refers to the named graph G1:. Following this approach, we refine the semantics of the AFF4 information model to imply that for any information segment, the statements implied by interpreting the content of the segment are defined to exist within a named graph based on the following conventions:

The graph name is the URN of the volume when the information segment is in the root of the volume.

The graph name is the URN interpretation of the path when the information segment exists in a sub-path of the volume.

Consider, for example, an AFF4 ZIP container containing a ZIP file comment urn:aff4:6cd61-52398e-4942ea and the two information segments in the listing:

1 /information.turtle 2 /urn%3Aaff4%3A19d6cd61-598e-49ff/information.turtle
The RDF statements contained in the first segment would be interpreted to exist in a named graph with the URN of the AFF4 volume urn:aff4:6cd61-52398e-4942ea. The RDF triples contained in the second segment would be interpreted as being contained in the graph named urn:aff4:19d6cd61-598e-49ff after decoding the filesystemfriendly encoding.

Provenance-related statements employ the named graph semantics in their statements. Consider, for example, the recording of the provenance of the information describing an image generated by the command line tool aff4imager. An abridged set of statements is presented in the listing:

1 @prefix G1: <urn:aff4:19857a87-a190b2f87> 2 @prefix G2: <urn:aff4:0a1fc78a-927bfacef> 3 @prefix T1: <urn:aff4:652e4027-ffff01199> 4 @prefix I1: <urn:aff4:9003027a-11199ffff> In this example, we define an instance T1: that represents the tool and an instance I1: that represents the image. The aff4:asserts predicate is used to specify that the tool "asserted" the information contained in the graph G1:. By identifying instances of type aff4:Tool and then identifying the graph in which the statements are located, downstream consumers of AFF4 containers would be able to identify the tool that generated specific information and data. While it is not related to provenance, note that the type ^^aff4:md5 in Line 14 indicates the data type of the text preceding it within quotes. In this case, it indicates that the value of the aff4:hash predicate is the hex-encoded MD5 message digest of the image.

Authentication and Non-Repudiation

With a means for referring to sets of statements in place, the approach to authentication and non-repudiation of evidence can be been refined. We conceptualize the relationship of signing containers in a manner similar to the approach proposed in [START_REF] Carroll | Named graphs, provenance and trust[END_REF]. An identity remains a person or entity as in the earlier AFF4 implementation. A warrant graph is a set of statements that record the intentions or beliefs of an identity about another set of statements, whether it be asserting, denying or quoting. The identity vouches for the truth of the warrant graph by signing the graph with a public key.

The following listing contains a warrant graph that refers to the aff4imager information presented in the listing above:

1 @base: <aff4://1b056380-a0911-f06721> 2 @prefix G2: <urn:aff4:0a1fc78a-927bfacef> 3 @prefix G3: <aff4://19857a87-a190b-2f87ab> 4 @prefix A1: <aff4://502ffb11-00f10-7fcbaf> 5 6

G3: { 7 G2: aff4:assertedBy G3: 8 G3: aff4:hash "TljN2NiNzExMmEwM2MxNG" ^^aff4:canonical-sha256 9 G3: aff4:authority A1: 10 A1: aff4:certificate A1:/cert.pem 11 G3: aff4:signature "XSAFfbgEL5C8vA1W/W-=" ^^aff4:canonical-sha256-rsa 12 }

The following observations can be made with regard to the listing: Line 7 refers to the graph G2: from the previous listing. This statement indicates that the warrant graph asserts the truth of G2:. Any number of named graphs may be asserted (or denied or other) within a warrant graph.

The graph digest of graph G3: is stated in Line 8. For serialization independence, a graph digest is a message digest with the canonical form of a set of triples in a named graph rather than the serialized syntax. This facilitates the verification of the authenticity of the target graph. The graph canonicalization method is specified by the type parameter aff4:canonical-sha256, and is a variant of the graph canonicalization algorithm in [START_REF] Carroll | Signing RDF graphs[END_REF] and the digest and signature methods defined in the XML signature standard [START_REF] Bartel | XML-Signature Syntax and Processing[END_REF]. The type parameter additionally indicates that the graph digest uses the SHA-256 digest on the canonical graph.

Line 9 states that the identity A1: authorizes the warrant graph.

Line 10 states that the public key certificate of A1: is found at the URN A1:/cert.pem.

Line 11 states the signature of G3: (warrant graph). The type ^^aff4:canonical-sha256-rsa indicates the method by which the signature was constructed, which was to take the warrant graph, canonicalize as above, take the SHA-256 hash, sign it using the RSA private key of the authority A1:, and then encode it using Base64.

The verification of a signed AFF4 container involves identifying a signed warrant graph, removing the aff4:signature statement from the graph, canonicalizing the resulting graph, and then re-verifying the calculated SHA-256 RSA signature. Recalculating the graph digests of graphs asserted by the warrant graph further authenticates the information contained in the graphs.

The use of named graphs, graph digests and graph signatures facilitates the piecewise generation of authenticable and non-repudiable information in the AFF4 universe.

AFF4 Data Model

AFF4 defines two abstractions for storing and representing bitstream data: the Stream and the Map. Instances of each of these abstractions are identified by an AFF4 URI.

The lowest layer of abstraction for data storage in the AFF4 data model is the Stream, an abstraction of a contiguous, randomly-accessible byte sequence. AFF4 defines a number of implementations for storing and accessing Streams ranging from an efficient randomly-accessible compressed container to a flat raw file.

The Map abstraction similarly represents a contiguous, randomlyaccessible byte array; however, it is composed of byte arrays from multiple stream sources. Defining virtual data objects as comprising portions of existing concrete data sources enables references to data objects within images (e.g., files) or data objects composed of multiple images (e.g., reconstructed RAID volumes). Maps are used as the fundamental building block for representing the data portions of files, partitions, unallocated space and reconstructions of virtual RAID volumes from images. Backward compatibility with EWF images is provided by creating a virtual image that maps to each compressed EWF segment.

10.

Refining the AFF4 Data Model AFF4 applications have revealed two shortcomings of the data model: (i) referring to subranges of data within a Stream is heavyweight, requiring the definition of a Map; and (ii) the data model does not support discontinuities that occur in evidence sources such as RAM and faulty hard drives.

10.1

Referring to Byte Ranges AFF4 requires a means to refer to arbitrary address ranges (slices) within AFF4 data objects. This is useful for a number of applications, including the annotation of content in TCP streams with the time of transmission, documenting provenance-related features of the derivation of an analytic product (e.g., file metadata), and describing the piecewise hash value of a chunk of an image.

An AFF4 slice provides the means to refer to a subrange within a URI. It is expressed by specifying the range within the fragment component of the URI:

URI#[offset:length]
The URI is a regular AFF4 Stream URI. The offset is a number that indicates the byte offset within the stream address range and the length is the number of bytes from the offset. For example, the slice URI: urn:aff4:195bdf58-1bc9-4ba4-9a9c-f1c312673fbf# [512,128] represents the address range from offset 512 to 640 in the URI.

urn:aff4:195bdf58-1bc9-4ba4-9a9c-f1c312673fbf

Note that the slice URI corresponds to an address range. In cases where the address range is backed by a stream of actual data, it also serves as a surrogate for the data within the bounds of the range. In the case where there is no corresponding data, it is a surrogate for the absence of data (i.e., an address space hole).

An example of a slice URI is demonstrated using a prototype piecewise hashing tool. Consider the following slice URI: urn:aff4:f37648c1#[0,2048] aff4:hash "c35f2ba345"^^aff4:sha256

The interpretation of the slice URI (which has been truncated for presentation) is that the content of the byte range from 0 to 2048 of the stream urn:aff4:f37648c1 has a SHA-256 value of c35f2ba345.

Representing Discontiguous Data

With the exception of the original AFF, existing forensic formats do not provide support for accurately imaging discontiguous data sources. Examples of discontiguous data sources include disks with read errors in certain sectors and the physical and virtual memory of computers with address space holes. For reasons of accuracy and completeness, it is important that the evidence container identifies areas of the Stream address space where there is no corresponding data, and potentially, the reason for the absence of data.

AFF4 provides a general solution to this problem by refining the semantics of the Map abstraction. Whereas the Map abstraction initially required that the target be a URI that resolves to a Stream or a Map, the refinement additionally allows the inclusion of a specially-defined URI as a target. Such a URI may indicate the characteristics of a byte range. For example, consider the imaging of a hard disk with a bad sector. We define a Map to represent the address space of the original evidence device and record the data content in a regular Stream. The Map records correspondences between the data content in the original device and the Stream. Figure 2 illustrates the mapping between the address space of an acquired hard drive with read errors and the underlying storage Stream. Note that the backing store stores valid data back to back, while the Map provides a view of the data with missing data represented as holes.

The address discontinuity that corresponds to the read error is given the target URI aff4:UnknownData. The following listing shows a Map segment that describes a discontinuity in this manner: 11.

Representing Data Patterns

Storage media commonly comes from the factory with the data content of every byte set to zero. With hard drives rapidly increasing in capacity, it is often the case that large runs of data within images contain zeros ("zero data runs"). The AFF4 format reduces the storage impact of zero data runs by compressing the runs. However, due to the uniform chunking method, there is the potential for considerable repetition in sources containing large numbers of zero data runs.

Known data runs may be expressed in AFF4 using the slice URI and Map facilities. For zero runs, we define a special purpose URI with semantics similar to the UNIX /dev/zero to represent a Stream containing an unbounded number of zeros. This URI is http://afflib.org/2009 /aff4#ZeroFilledByteRange.

Of relevance to referencing common data patterns is recent work related to Teleporter [START_REF] Watkins | Teleporter: An analytically and forensically sound duplicate transfer system[END_REF], which explores the efficient transmission of forensic images by sending certain data runs of the image with reference to a standard corpus of files. Thus, in the case of a common file such as ntfs.dll, Teleporter would transport a fingerprint of the file rather than the entire data content. The receiver would then reconstitute the data content of the file from local sources.

Conclusions

The refinements made to the information and data models of the AFF4 evidence container format address the accurate representation of discontiguous data, help describe the provenance of stored evidence, and support authentication and non-repudiation of data and information by cryptographic signing.

Prototype implementations of AFF4 have been written in C, Python and Java. Our future research will integrate AFF4 with the PyFlag network forensic environment, the Volatility volatile memory analysis framework and the Sleuth Kit filesystem analysis tool. Also, it will ensure that AFF4 provides backward compatibility with the raw, EWF and AFF1 evidence container formats.

Figure 2 .

 2 Figure 2. Address space mapping of a discontiguous evidence source.

  urn:aff4:da0d1948-846f-491d-8183-34ae691e8293 2 4096,0,http://libaff.org/2009/aff4#UnknownData 3 8192,4096,urn:aff4:da0d1948-846f-491d-8183-34ae691e8293

Table 1 .

 1 Comparison of representational capabilities of container formats.

						Data Representation
			raw EWF sgzip LE1 DEB SDEB AFF1 AFF4
	Single Image Sto-	Y	Y	Y	N	Y	Y	Y	Y
	rage
	Multiple Image Sto-	N	N	N	N	Y	Y	N	Y
	rage
	Hierarchical Image	N	N	N	Y	Y	Y	N	Y
	Storage	(Logical
	Imaging)
	Addressing Windo-
	ws (Discontiguous
	Images)

!"#$%&$ '(()%*#+%,& -#./%&$ '(()%*#+%,& 0%)1.2.+1" !&+13(31+13 0%)145#36%&$ '(()%*#+%,& 7%.8 !"#$1 9%1*1:%.1 -#./1. '(()%*#+%,&. % : +/4'00; <=((,3+ <%$&#+=31 0%)1.4> ?1+# #+# !&#)),*#+1 <(#*1 5#361 0%)1. '00;4 ",)="1 <%$&%&$ '(()%*#+%,&

  Figure 1. Layered application of forensic tools with the AFF4 container.


Néstor Bohórquez

Pierre-Brice Wieber

Adaptive step duration in biped walking: a robust approach to nonlinear constraints

When a biped robot is walking in a crowd, being able to adapt the duration of steps is a key element to avoid collisions. Model Predictive Control (MPC) schemes for biped walking usually assume a fixed step duration since adapting it leads to a nonlinear problem, in general. Nonlinear solvers do not guarantee the satisfaction of nonlinear constraints at every iterate and this can be problematic for the real-time operation of robots. We propose a method to make sure that all iterates satisfy the nonlinear constraints by borrowing concepts from robust control: we make the problem robust to nonlinearities within some bounds. These bounds are linear with respect to the variables of the problem and can be adapted online.

I. INTRODUCTION

When walking in a crowd, a biped robot should naturally try to avoid collisions with people. One strategy to do this is to adapt the position of steps in response to the motion of the crowd. This can be formulated as a linear problem if one considers the duration of steps to be fixed, as usually done [START_REF] Herdt | Online Walking Motion Generation with Automatic Foot Step Placement[END_REF], [START_REF] Diedam | Online walking gait generation with adaptive foot positioning through linear model predictive control[END_REF], [START_REF] Englsberger | Three-dimensional bipedal walking control based on divergent component of motion[END_REF]. Nevertheless, the combination of maximal step length and fixed step duration limits the maximal speed the robot can achieve and, consequently, its ability to avoid collisions [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF]. We need, therefore, to adapt the duration of the steps of the robot.

However, by doing this, the problem becomes either nonlinear or combinatorial, depending on whether we choose to vary the duration of the steps in a continuous or discrete manner. On the continuous side, nonlinear MPC schemes have been proposed using Sequential Quadratic Programming (SQP) [START_REF] Aftab | Ankle, hip and stepping strategies for humanoid balance recovery with a single model predictive control scheme[END_REF] or Interior Point (IP) methods [START_REF] Kryczka | Online regeneration of bipedal walking gait pattern optimizing footstep placement and timing[END_REF]. On the discrete side, these MPC schemes have been formulated as Mixed Integer Quadratic Programs [START_REF] Ibanez | Emergence of humanoid walking behaviors from mixed-integer model predictive control[END_REF]. Alternatively, others have shown that the problem of adapting the duration of the steps can be made completely linear if we either: 1) limit the number of steps in the future to one [START_REF] Khadiv | Step timing adjustment: A step toward generating robust gaits[END_REF] or 2) consider the relation between the Capture Point and the positions of the future footsteps [START_REF] Griffin | Walking stabilization using step timing and location adjustment on the humanoid robot, atlas[END_REF]. However, it is not clear whether these two last approaches are suitable for making a robot walk in a crowd: the first one proposes a preview horizon that might be too short and the second does not account explicitly for the motion of the Center of Mass (CoM).

Standard solvers for nonlinear problems (SQP and IP methods) implement a form of Newton method in which constraints are iteratively linearized. However, the satisfaction of these linearized constraints does not imply the satisfaction of the original nonlinear constraints. There is no guarantee that the nonlinear constraints are satisfied at every Newton Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP*, LJK, 38000 Grenoble, France nestor-alonso.bohorquez-dorante, pierre-brice.wieber@inria.fr.

iterate. This is a problem for real-time operation where we may need to interrupt the solver before convergence and still need a solution that can be applied safely to the robot. This issue has been reported in [START_REF] Caron | Dynamic Walking over Rough Terrains by Nonlinear Predictive Control of the Floating-base Inverted Pendulum[END_REF] but for a different humanoid locomotion problem.

We propose here a method to guarantee safe Newton iterates. It is similar to what was done in [START_REF] Brasseur | A robust linear MPC approach to online generation of 3d biped walking motion[END_REF], [START_REF] Serra | A Newton method with always feasible iterates for Nonlinear Model Predictive Control of walking in a multi-contact situation[END_REF] for the problem of adapting the vertical motion of the CoM of the robot: we design constraints that are robust to changes in the variable that introduces the nonlinearity. To do so, we make sure the constraints are feasible over a given interval of this variable. We can then make safe linear approximations of the objective function inside of this interval and always generate feasible iterates.

With this method it suffices to solve a single Quadratic Program (which takes 0.29[ms] on average) to obtain a feasible solution. Simulations show that, by adapting the step duration in this way, we can reduce the collision rate of the robot walking in a crowd from 75% to less than 6%.

We proceed as follows: in Section II we present the specific nonlinearity that we face when we adapt the duration of the steps and how we develop robustness with respect to it. We then apply this technique for robustness to all dynamic, kinematic and collision avoidance constraints of the robot in Section III. We introduce in Section IV the Optimal Control Problem (OCP) we need to solve. Finally, we present some numerical results that showcase the capabilities of our controller in Section V.

II. PROBLEM DEFINITION

The motion of the CoM of a biped walking robot is commonly modeled as a triple integrator [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF] x

+ = ⎡ ⎣ 1 τ τ 2 /2 0 1 τ 0 0 1 ⎤ ⎦ x + ⎡ ⎣ τ 3 /6 τ 2 /2 τ ⎤ ⎦ ... c , (1)
where c is the position of the CoM, the jerk ... c is the input of the system, x = (c, ċ, c) and x + = (c + , ċ+ , c+ ) are two consecutive states. Here, the jerk is considered to be constant over intervals of time of length τ that we define to be 1/8 th of the duration of one step of the robot. The successor state x + is linear with respect to ... c but nonlinear with respect to τ . In particular, x + is a cubic polynomial of τ . The value of τ is commonly set to a constant in order to obtain a completely linear formulation.

We base our approach for adapting the duration of the steps on varying τ , what gives a nonlinear problem to solve.

β 0 = x + (τ ) β 0 + t * ∂x + ∂τ (τ ) = β 2 + u * ∂x + ∂τ (τ ) = β 1 β 2 = x + (τ )
x + (τ )

Fig. 1: Boundaries of x + (τ ) defined as the convex hull of its Bernstein coordinates (β 0 , β 1 , β 2 ). The control points β 0 and β 2 are located at x + (τ ) and x + (τ ), respectively. The control point β 1 is located at the intersection of the lines tangent to x + (τ ) and x + (τ ).

We propose to restrict τ to an interval [τ , τ ] and build bounds on x + (τ ) that depend on τ , τ but not on τ . The complexity of the bounds that we define on x + (τ ) depend on the degree of the polynomial involved. In order to simplify this issue, we reduce the degree of x + (τ ) by rewriting the last equation of (1) as

... c = c+ - c τ , (2)
and substituting it back in the triple integrator to obtain:

x + = ⎡ ⎣ 1 τ τ 2 /3 0 1 τ /2 0 0 0 ⎤ ⎦ x + ⎡ ⎣ τ 2 /6 τ /2 1 ⎤ ⎦ c+ . (3)
In this way, the successor state x + (τ ) is a quadratic polynomial of τ that preserves the C 2 continuity of the motion of the CoM. We define the bounds on x + (τ ) by changing its representation from the monomial basis {1, τ, τ 2 } to the Bernstein basis [START_REF] Lorentz | Bernstein polynomials, ser. Mathematical expositions[END_REF]:

{b 0 (τ ), b 1 (τ ), b 2 (τ )}, (4)
(traditionally used in Bézier curves) where

b 0 (τ ) = (1 -τ ′ ) 2 , b 1 (τ ) = 2τ ′ (1 -τ ′ ), b 2 (τ ) = τ ′2 , (5)
and

τ ′ = τ -τ τ -τ , (6)
for a given choice of τ , τ . These polynomials have the desirable property that for all τ ∈

[τ , τ ], b i (τ ) ∈ [0, 1], b i (τ ) = 1 and therefore x + (τ ) = 2 i=0 β i b i (τ ) ∈ conv{β i }. (7)
So, the polynomial x + (τ ) is always contained in the convex hull of the points β 0 , β 1 , β 2 whenever τ ∈ [τ , τ ], as can be seen in Figure 1. These points can be interpreted geometrically as control points of x + (τ ). Details on the transformation from monomial to Bernstein coordinates can be found in the Appendix.

III. CONSTRAINTS ROBUST TO THE STEP DURATION A. Constraint on the steps

We introduce a constraint on the sequence of steps made by the robot (s 1 , . . . , s J ) to prevent it from crossing legs while walking:

s j+1 -s j ∈ S j . (8)
The set S j alternates between left and right according to s j .

B. Constraint on the CoP

When the robot is walking with its CoM at a constant height over a horizontal flat ground, the position of the Center of Pressure (CoP) can be written as:

p + (τ ) = 1 0 -h/g x + (τ ), ( 9
)
where h is the height of the CoM and g is the norm of the gravity vector. Due to the unilaterality of the contact forces with the ground, the CoP can only reside inside the support polygon of the robot, which is a convex set P translated to the j th footstep position s j :

p + (τ ) -s j ∈ P. (10)
This involves a quadratic polynomial of τ that can be expressed in Bernstein basis as outlined earlier:

p + (τ ) -s j = λ i b i (τ ) ∈ conv{λ i }, (11)
where

λ i = 1 0 -h/g β i -s j .
We can enforce this nonlinear constraint for all τ ∈ [τ , τ ] by imposing instead that ∀i :

λ i ∈ P, (12)
since by definition of the Bernstein basis:

∀i : λ i ∈ P =⇒ p + (τ ) -s j ∈ P. (13)
As mentioned before, each λ i is linear with respect to the initial state x and the control input c+ . By satisfying the linear constraints on {λ i } we satisfy the nonlinear constraints on p + (τ )s j .

C. Constraint on the CoM

Since the length of the legs is limited, we do not allow the CoM to be far from the position of the footsteps. We define a convex set C j that represents the possible positions of c + (τ ) with respect to s j :

c + (τ ) -s j ∈ C j . ( 14
)
The set C j alternates between left and right accordingly. Since c + (τ ) = 1 0 0 x + (τ ), this involves the quadratic polynomial

c + (τ ) -s j = π i b i (τ ) ∈ conv{π i }, (15)
where π i = 1 0 0 β is j . Then, by enforcing the linear constraint ∀i :

π i ∈ C j , (16)
we make sure that the nonlinear constraint ( 14) is satisfied for all τ ∈ [τ , τ ] since ∀i :

π i ∈ C j =⇒ c + (τ ) -s j ∈ C j . (17)

D. Constraint on collision avoidance

In order to avoid collisions, we want the CoM of the robot to be at least a certain distance d from each person m k in the environment:

∀k : ∥c + (τ ) -m k (τ )∥ 2 ≥ d. (18)
If we define m k (τ ) = µ i b i (τ ) then this constraint involves, again, the quadratic polynomial

c + (τ ) -m k (τ ) = σ i b i (τ ) ∈ conv{σ i }, (19)
where

σ i = 1 0 0 β i -µ i .
We define σ as the centroid of the control points {σ i } and B i as a ball centered at the origin with radius d + ∥σσ i ∥ 2 . We enforce the linear constraint

∀i : σ / ∈ B i , (20)
which is a sufficient condition for the satisfaction of the nonlinear constraint (18) for all τ ∈ [τ , τ ], that is

∀i : σ / ∈ B i =⇒ ∀k : ∥c + (τ ) -m k (τ )∥ 2 ≥ d. (21)

E. Constraint on capturability

In order to impose 0-step capturability at the end of the horizon, we conduct the last position of the Capture Point ξ N to the interior of the support polygon of the robot

ξ N (τ ) -s J ∈ P. (22)
Given that ξ + (τ ) = 1 h/g 0 x + (τ ) we can write, once again, the quadratic polynomial

ξ N (τ ) -s J = ψ i b i (τ ) ∈ conv{ψ i }, (23)
where ψ i = 1 h/g 0 β is J , and check the linear constraint ∀i :

ψ i ∈ P, (24)
which is sufficient to ensure the 0-step capturability of the robot for all τ ∈ [τ , τ ] ∀i :

ψ i ∈ P =⇒ ξ N (τ ) -s J ∈ P. (25)
F. Adapting the positions of the steps as a function of their duration Constraints ( 10), ( 14) and ( 22) are not always possible to satisfy with a single choice of s j for all values of τ . In particular, constraint [START_REF] Caron | Dynamic Walking over Rough Terrains by Nonlinear Predictive Control of the Floating-base Inverted Pendulum[END_REF] is the most restrictive as can be easily seen in Figure 2: different trajectories of the CoP for different τ do not fit all inside a single sequence of steps.

We propose to vary the positions of the steps of the robot as a linear function of τ :

(s 1 (τ ), . . . , s J (τ )). (26)
To do so, we choose to relate the positions of the steps to the positions of the CoP by defining s j (τ ) as the centroid of P j (τ ):

s j (τ ) = 1 N j P j (τ ) + s ′ j , (27)
where P j (τ ) is the set of all future positions of the CoP belonging to the j th future step and N j is the cardinality of this set. The free parameter s ′ j adds flexibility in the choice of the position of the footstep.

By doing this, constraint ( 8) is now a polynomial of τ (and, therefore, of the step duration) and the polynomials ( 11), (15), (23) change to

s j+1 (τ ) -s j (τ ) = γ i b i (τ ), p + (τ ) -s j (τ ) = λ ′ i b i (τ ), c + (τ ) -s j (τ ) = π ′ i b i (τ ), ξ N (τ ) -s J (τ ) = ψ ′ i b i (τ ). (28)
Consequently, their respective sufficient conditions for feasibility become ∀i :

γ i ∈ S j , λ ′ i ∈ P, π ′ i ∈ C j , ψ ′ i ∈ P. (29)

IV. MODEL PREDICTIVE CONTROL FOR WALKING

Having defined robust constraints with respect to an interval of τ , we can safely choose any value τ * ∈ [τ , τ ] that minimizes a given cost function. The desired behaviour of our robot, reflected in this cost function, is to: 1) keep each person in the crowd at a comfortable distance, i.e. no less than d ref from the CoM, 2) move the CoM at a reference velocity ċref , 3) keep the CoP at the center of the foot for improved balance, 4) minimize the jerk of the CoM for smoothness of its motion and regularization, 5) penalize step durations different from a given reference value 8τ ref where energy expenditure is optimal and 6) stop the robot at the end of the horizon to ensure capturability. In summary, we consider the following objectives:

o 1 : ∥c + (τ ) -m k (τ )∥ 2 ≥ d ref > d ∀k, o 2 : ċ+ (τ ) =ċ ref , o 3 : p + (τ ) -s j (τ ) =0, o 4 : ... c (τ ) = 0 , o 5 : τ = τ ref , o 6 : p N (τ ) =ξ N (τ ), (30)
altogether as f (c + , τ, s ′ j ) ≤ q in the following OCP over a horizon of length N :

minimize c+ ,τ,s ′ j ,v ∥v∥ 2 2
subject to

f (c + , τ, s ′ j ) + v ≤ q (20), (29) τ ∈ [τ , τ ]. (31)
The function f is nonlinear with respect to τ so we apply a Newton method and consider successive linearizations. After each iteration we can adapt, for the next iteration, the interval [τ , τ ] based on the previous optimal τ * :

τ = τ * - ∆τ 2 , τ = τ * + ∆τ 2 . ( 32
)
We propose to keep ∆τ constant.

V. SIMULATION RESULTS

We evaluate the performance of our controller by simulating a robot and a crowd walking in opposite directions. As in [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF], we assume that: people walk at constant velocities, they do not try to avoid the robot and collisions among people are disregarded. The parameters of the robot are specified in Table I.

A. Typical behaviour

k {-1, -1.25, -1.5} m.s -1 ṁy k N (0, 0.2) m.s -1 Length of interval step duration ∆τ {0 , 0.5, 1, 2, 4, 8} ms
obstacles present in the Field of View (FoV). The robot walks freely and tries to reach its reference velocity ċref making steps of nominal duration (0.8[s]). Between 2[s] and 16[s] the robot encounters people walking in opposite direction and moves backwards to avoid them. At first (between 2[s] and 3[s]) the robot only makes larger steps while maintaining its nominal step duration. However, its maximal speed under such conditions is only about -0.75m.s -1 whereas people in the crowd walk at -1.5m.s -1 . Consequently, it is forced (between 3[s] and 11[s]) to also make faster steps to be able to avoid collisions. At 11[s] the robot resumes its forward walking motion once it has overcome most people in its way. It has to stop occasionally a couple of times to walk around the last members of the crowd. From 16[s] until 20[s] the robot continues walking uninterrupted at its objective velocity.

The adaptation of [τ , τ ] allows the robot to avoid infeasibilities due to difficult collision-avoidance situations. The key here is objective o 1 : it makes the cost function take into account potential collisions in the future so that the optimal solution (c * , τ * , s * j ) moves the system away from infeasibilities.

B. Effect of the length of the interval of τ

We investigate the effect of ∆τ on the ability of the robot to avoid collisions with the crowd. We make 900 simulations A longer interval leads to a more constrained OCP that is more likely to become infeasible, which is what is shown in the left plot of Figure 4. For ∆τ ∈ {0.5, 1}[ms] this issue occurs less than 2% of the time and for ∆τ = 2[ms] this rises to 9%. When the OCP becomes infeasible we can continue executing the last computed trajectory until the OCP becomes feasible again. If this does not happen, the last computed trajectory ensures that the robot will come to a stop before any collision happens, as in [START_REF] Bohórquez | Safe navigation strategies for a biped robot walking in a crowd[END_REF].

The plot on the right of Figure 4 shows the proportion of such outcomes. No collisions occur when the speed of the crowd is less than 1.5[m.s -1 ] for any of the intervals we proposed. When the crowd reaches this speed collisions do occur: 1) with ∆τ ∈ {0.5, 1}[ms] because people move faster than what the robot can adapt its step duration; 2) with ∆τ = 8[ms], due to the high number of consecutive infeasible OCPs that make the robot stop in the middle of the walking crowd.

A choice of ∆τ = 1[ms] appears, therefore, to be the best option. The improvement in collision avoidance we obtain over a controller with fixed τ = 0.1[s], shown in Figure 4 as ∆τ = 0, is clear for the speeds of the crowd we considered.

C. Computational efficiency

The OCP (31) contains 41 decision variables. The number of constraints is proportional to the number of obstacles in the FoV (less or equal to M ). This number is multiplied by three due of the robustness we introduce using the Bernstein basis. In our simulations the total number of constraints oscillates between 500 and 900. A single iteration of this problem is solved on average in 0.29[ms] on a laptop with a 3[GHz] Intel Core i7 CPU.

VI. CONCLUSIONS

We presented a method to adapt the duration of the steps of the robot to improve its ability to avoid collisions when walking in a crowd. It is based on varying τ in a continuous manner while guaranteeing the satisfaction of nonlinear constraints at every Newton iteration. To do so, we identified bounds on the state of system for a given interval of τ and we made sure that the bounds satisfied all constraints. Solving a single carefully constructed Quadratic Program was sufficient to obtain a feasible solution. We reduced significantly the collision rate of the robot from 75% to less than 6%. In the future, we would like to apply this method to locomotion problems with multiple contacts where timing is a critical issue. APPENDIX Given a quadratic polynomial x(τ ) for τ ∈ [τ , τ ] with coordinates α = (α 0 , α 1 , α 2 ) in the monomial basis {1, τ, τ 2 }, we first find the equivalent coordinates in the normalized monomial basis {1, τ ′ , τ ′2 }, for τ ′ ∈ [0, 1], by defining τ = τ + (ττ )τ ′ and solving for all τ ′

α 0 + α 1 τ + α 2 τ 2 = α ′ 0 + α ′ 1 τ ′ + α ′ 2 τ ′2 , to obtain ⎡ ⎣ α ′ 0 α ′ 1 α ′ 2 ⎤ ⎦ = ⎡ ⎣ 1 τ τ 2 0 τ -τ 2(τ -τ )τ 0 0 (τ -τ ) 2 ⎤ ⎦ ⎡ ⎣ α 0 α 1 α 2 ⎤ ⎦ .
Then we find its coordinates β = (β 0 , β 1 , β 2 ) in the Bernstein basis {(1τ ′ ) 2 , 2τ ′ (1τ ′ ), τ ′2 } by solving, once again, for all τ ′

α ′ 0 + α ′ 1 τ ′ + α ′ τ ′2 = β 0 (1 -τ ′ ) 2 + β 1 2τ ′ (1 -τ ′ ) + β 2 τ ′2 , to obtain: ⎡ ⎣ β 0 β 1 β 2 ⎤ ⎦ = ⎡ ⎣ 1 0 0 1 1/2 0 1 1 1 ⎤ ⎦ ⎡ ⎣ α ′ 0 α ′ 1 α ′ 2 ⎤ ⎦ .

Fig. 2 :

 2 Fig.2: Future trajectories of the CoP for τ = τ (in yellow) and τ = τ (in blue). Figures show future steps that do not vary with τ (on the left) and that vary with τ (on the right). The circle represents the body of the robot, the filled rectangle is the current step, the unfilled rectangles are the previewed future steps.

Figure 3

 3 Figure3shows the results obtained from one illustrative simulation. The parameters of the controller and the crowd are specified in TableII. During the first 2[s] there are no

Fig. 3 :

 3 Fig. 3: Adapting the step duration while walking in a crowd. The top subfigure shows in solid blue the x component of the steps (s x jc x ) made by the robot during the simulation. Values above and below the red line indicate forward and backward motion, respectively. The vertical dashed lines mark the instants at which steps were made. The magenta dashed lines indicate the maximal step the robot can make. The bottom subfigure shows the x component of the velocity of the robot ( ċx ) during the simulation. The magenta dashed lines indicate the maximal speed the robot can reach at a nominal step duration of 0.8[s]. The green dash-dotted line indicates the objective speed.

Fig. 4 :

 4 Fig. 4: Infeasible iterations and collision rate for different lengths of interval of τ .

TABLE I :

 I Parameters of biped robot

	Parameter	Symbol	Value	Unit
	CoM height (9)	h	0.80	m
	Feet dim. (10)	P	0.25 × 0.125	m × m
	Leg stride (14)	C j	0.30 × 0.30	m × m
	Feet separation (8)	S j	0.21	m
	Safety dist. (18)	d	1	m
	Radius of FoV	R	6	m
	Horizon length	N	18	samples
	Double supp. dur.	τ	-	s
	Single supp. dur.	7τ	-	s
	Ref. step dur. (30)	8τ ref	0.8	s
	Comfort dist. (30)	d ref	3	m
	Ref. vel. (30)	ċref	(0.5, 0)	(m.

s -1 , m.s -1 )

TABLE II :

 II Parameters of scenario A

	Parameter	Symbol	Value	Unit
	Size of crowd	M	16	persons
	Vel. of the crowd	ṁx k ṁy k	-1.5 N (0, 0.4)	m.s -1 m.s -1
	Length of interval of step duration	∆τ	5	ms

TABLE III :

 III Parameters of scenario B

	Parameter	Symbol	Value	Unit
	Size of crowd	M	16	persons
	Vel. of the crowd	ṁx

ACKNOWLEDGMENTS

This work has been funded by the PSPC Romeo 2 project and EU H2020 Comanoid Research and Innovation Action (RIA).