Andreas Follner
email: andreas.follner@cased.de

Alexandre Bartel
email: alexandre.bartel@cased.de

Eric Bodden
email: bodden@acm.org

Eric Bodden Analyzing

Analyzing the Gadgets Towards a Metric to Measure Gadget Quality

Keywords: ROP, gadgets, exploit, CFI, MPX, metrics

Current low-level exploits often rely on code-reuse, whereby short sections of code (gadgets) are chained together into a coherent exploit that can be executed without the need to inject any code. Several protection mechanisms attempt to eliminate this attack vector by applying code transformations to reduce the number of available gadgets. Nevertheless, it has emerged that the residual gadgets can still be sufficient to conduct a successful attack. Crucially, the lack of a common metric for "gadget quality" hinders the effective comparison of current mitigations. This work proposes four metrics that assign scores to a set of gadgets, measuring quality, usefulness, and practicality. We apply these metrics to binaries produced when compiling programs for architectures implementing Intel's recent MPX CPU extensions. Our results demonstrate a 17% increase in useful gadgets in MPX binaries, and a decrease in side-effects and preconditions, making them better suited for ROP attacks.

Introduction

Several mitigation techniques guarding against control-flow attacks have been developed over the past 15 years. In contrast to modern-day attacks [START_REF] Carlini | Control-flow bending: On the effectiveness of control-flow integrity[END_REF][START_REF] Carlini | Rop is still dangerous: Breaking modern defenses[END_REF][START_REF] Conti | Losing control: On the effectiveness of controlflow integrity under stack attacks[END_REF][START_REF] Davi | Stitching the gadgets: On the ineffectiveness of coarse-grained control-flow integrity protection[END_REF][START_REF] Göktas | Out of control: Overcoming control-flow integrity[END_REF][START_REF] Li | Emerging stack pivoting exploits bypass common security[END_REF][START_REF] Schuster | Counterfeit object-oriented programming: On the difficulty of preventing code reuse attacks in c++ applications[END_REF][START_REF] Schuster | Evaluating the effectiveness of current anti-rop defenses[END_REF][START_REF] Snow | Just-in-time code reuse: On the effectiveness of fine-grained address space layout randomization[END_REF][START_REF] Sotirov | Heap feng shui in javascript[END_REF], the attacks of the 90s [START_REF] One | Smashing the stack for fun and profit[END_REF] were simple. The latter typically exploited a stack-based buffer overflow vulnerability to overwrite a stack frame's return address with another that points to a location at which the attacker had previously injected malicious code. On returning from the compromised function, execution would consequently be redirected to the injected code block.

Since the early 2000s, the prevalent processor architectures have adopted the No-eXecute (NX bit) extensions. These allow an operating system to mark memory pages that only contain data (namely the heap and stack) as being non-executable [START_REF]Data execution prevention[END_REF], thus stopping code-injection attacks. However, programs may need to be able to allocate executable memory, for example for just-intime compilation [START_REF] Aycock | A brief history of just-in-time[END_REF]. For such cases, the operating system provides several API calls that can change the memory protection level of a memory area (e.g., VirtualProtect4 on Windows). These API calls were quickly abused by attackers, who would leverage them to change the access privileges of a region of memory where they had previously injected their payload. To circumvent the NX bit protection and to execute the API calls which change the memory protection of the payload code to executable, current exploits reuse executable code snippets, or gadgets, comprising code from the running program and loaded libraries. Such attacks are known as code-reuse attacks, the most popular and widespread technique being Return-Oriented Programming (ROP) [START_REF] Roemer | Return-oriented programming: Systems, languages, and applications[END_REF][START_REF] Shacham | The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86)[END_REF].

The difficulty of staging a ROP attack in practice is subject to an attacker's concrete aims, the underlying environment, and the available gadgets. The latter, in particular, varies enormously between binaries. However, there is currently no established metric for quantifying the utility of gadgets within a given binary. Having such a metric would enable the comparison of gadgets in various kinds of transformed binaries, e.g., different optimization levels of compilers, or binaries that have been rewritten to add instructions for exploit mitigation. Currently, many tools that produce such binaries, even those meant to enhance a binary's security, do not take into account how their transformation affects ROP gadgets. Especially for exploit-mitigation techniques this is counterproductive: if a mitigation technique transforms code, how does one know that it does not in the end increase a binary's attack surface by adding useful gadgets?

This work presents four metrics based on practical exploit development, that are designed to aid researchers in the evaluation of mitigations. More generally, these metrics allow one to determine whether a binary transformation introduces gadgets that are better suited for ROP attacks than the original binary.

Since it is somewhat difficult to make statements about the usefulness of a set of gadgets without knowing the goal of the attacker and the underlying environment, the metrics cover two targeted, real-world exploitation scenarios, and two more general computations which reflect gadget variety and gadget usability. This work further applies the metrics to binaries protected by MPX (Memory Protection eXtensions) [START_REF] Ramakesavan | Intel memory protection extensions (intel mpx) enabling guide[END_REF], a new buffer-overflow mitigation technique from Intel that adds instrumentation code to binaries through the compiler. As our evaluation shows, MPX-enabled binaries actually do contain more useful gadgets, and thereby increase the attack surface. This is particularly worrysome when running MPX-enabled binaries on legacy hardware that cannot benefit from the increased security that MPX is designed to offer. To summarize, our key contributions are:

a definition of four metrics to measure gadget quality, -GaLity, an open-source implementation to compute metrics on sets of gadgets, and a case study using the metrics to determine how MPX affects gadgets on eight representative Windows x64 binaries.

The remainder of this paper is organized as follows. Section 2 motivates the necessity to evaluate gadget quality. Section 3 describes the proposed metrics. Section 4 explains the conducted case study on MPX. Section 5 covers related work. Finally, Section 6 concludes the paper.

Motivation

To the best of our knowledge, there exists no metric to assess the quality of a gadget or a set of gadgets. Such a metric, however, has a large variety of use cases. For example, it could be used to compare different control-flow integrity (CFI) [START_REF] Abadi | Control-flow integrity[END_REF] approaches. Today's CFI implementations [START_REF] Cheng | Ropecker: A generic and practical approach for defending against rop attacks[END_REF][START_REF] Pappas | Transparent rop exploit mitigation using indirect branch tracing[END_REF][START_REF] Payer | Fine-grained control-flow integrity through binary hardening[END_REF][START_REF] Tice | Enforcing forward-edge control-flow integrity in gcc & llvm[END_REF][START_REF] Van Der Veen | Practical context-sensitive cfi[END_REF][START_REF] Zhang | Control flow integrity for cots binaries[END_REF] often use a metric which measures the reduction of gadgets (such as AIR, the average indirect target reduction [START_REF] Zhang | Control flow integrity for cots binaries[END_REF], or DAIR, the dynamic average indirect target reduction [START_REF] Payer | Fine-grained control-flow integrity through binary hardening[END_REF]) to compare their results. For many approaches, this metric shows a reduction of over 99%, yet this does not take into consideration the total number of gadgets, nor the quality of the remaining gadgets, limiting the metric's practical use. A DAIR of 90% that leaves 50 gadgets with many side effects and preconditions intact is likely more secure than a DAIR of 99.5%, that leaves intact exactly those 7 gadgets that an attacker requires to craft an exploit. Researchers using those metrics frequently acknowledge their limitations and the difficulty of developing a metric that measures gadget quality [START_REF] Carlini | Control-flow bending: On the effectiveness of control-flow integrity[END_REF][START_REF] Payer | Fine-grained control-flow integrity through binary hardening[END_REF][START_REF] Tice | Enforcing forward-edge control-flow integrity in gcc & llvm[END_REF].

In general, attackers favour simple gadgets which have a minimum of side effects and preconditions. For example, consider a gadget that loads the value that rsp points to into rax. A clean and effective gadget for achieving this would be: pop rax ; ret. In contrast, the gadget: pop rax ; push rsp ; pop rbp ; mov [rdi+0x34fa], rsp ; ret 0x2dbf1 will also achieve this aim, but will also have the side-effect of overwriting rbp. In addition, this gadget has the precondition that rdi+0x34fa has to point to writeable memory. Finally, ret 0x2dbf1 not only adds a large offset to rsp (which can be an issue if attackercontrolled memory is scarce, because it might set rsp to point outside of the allocated memory), it also disaligns the stack pointer, which is something normal programs do not do, hinting at a possible exploit execution. The next Section presents the four metrics we propose to compute gadget quality.

Metrics for Measuring Gadget Quality

In general, evaluating the quality of a set of gadgets is non-trivial. This stems primarily from the fact that an attacker's goal is potentially unknown, and that given sufficient gadgets, one can construct practically any program. In addition, the gadgets required for an attacker to achieve a goal vary by operating system and architecture. For example, on Windows x86, parameters to functions are usually passed on the stack, while on Windows x64, the first four parameters are passed through registers and all remaining ones are passed on the stack 5 , leading to differences in gadget requirements. As a running example, we consider exploits targeting VirtualProtect, which is an API call that commonly serves as an avenue to bypassing NX protection on Windows 7 x64 [START_REF] Ducklin | Anatomy of an exploit -inside the cve-2013-3893 internet explorer[END_REF][START_REF] Jurczyk | One font vulnerability to rule them all #2: Adobe reader rce exploitation[END_REF][START_REF] Pi | Unpatched flash player flaw, more pocs found in hacking team leak[END_REF]. We stress that our four metrics are not bound to evaluating this specific API call, as they consider the more general attack setup and execution procedures associated with ROP exploits. In addition, we perform an in-depth analysis of the various properties of gadgets with respect to their side effects, preconditions, usability, and usefulness.

Metric 1: Gadget Distribution

The gadget distribution metric is calculated by partitioning a given set of gadgets into twelve broad categories, with each category representing a class of operations, such as arithmetic and data move, as shown in Table 1. Gadgets are assigned to a category based on the first instruction of a gadget. For example, the gadget add rax, 0x40 ; pop rcx ; ret would be assigned to the arithmetic category. We categorize on the basis of the first instruction as every suffix of a gadget is itself a gadget, and will be categorized separately. Note that gadgets containing privileged or sensitive instructions [START_REF]Intel 64 and ia-32 architectures software developer's manual combined[END_REF] are discarded and not considered in further steps because they trap in user mode, thereby making a gadget unusable.

Analyzing the distribution of frequencies of gadgets amongst categories is helpful as it allows comparing whether the distribution of gadgets in a transformed binary is similar to the one in the original binary, or if the number of gadgets in a category useful for an attacker has grown. Gadget quality and usefulness, however, are not measured and addressed by the remaining metrics.

While Table 1 does not contain all instructions of the x86-64 instruction set, it covers 99% of the instructions found in gadgets of the binaries we used in the evaluation, i.e., a total of 20 MiB containing over one million instructions. Due to the large size of the x86-64 instruction set (over 700 instructions [START_REF]Intel 64 and ia-32 architectures software developer's manual combined[END_REF]), it would be a time-consuming, manual process to cover all existing instructions. However, the fact that we do not achieve 100% coverage does not pose a threat to the metric, because all important and common instructions are categorized. The few we we did not include do not have a big impact on the overall distribution. A manual inspection of uncategorized instructions in other binaries (we used several Windows 7 system libraries) revealed that there were many different instructions but in small numbers in any of the inspected binaries, which is what we expected.

Metric 1 allows to assess whether a transformed binary contains more gadgets in categories useful to an attacker.

Metric 2: Gadget Environment Setup Capabilities

When constructing a ROP exploit, an attacker must be able to prepare the environment and operands for subsequent gadgets in a chain. For example, when attempting to perform a Windows API call via ROP, an attacker will generally require the ability to specify the call's arguments. The degree of ease with which an attacker may manipulate memory will affect the choice of gadgets that she uses. In this metric, we consider the most general case, whereby an attacker is able to inject arbitrary arguments into a target program's memory space at a known location. This could be possible due to, e.g., a browser with Javascript turned on, allowing heap sprays and Heap Feng Shui [START_REF] Sotirov | Heap feng shui in javascript[END_REF], and other vulnerabilities like information leaks [START_REF] Serna | The info leak era of software exploitation[END_REF]. We further assume the vulnerable program is running on a Windows 7 x64 machine, which is a very common platform. Consider the case whereby an attacker wants to invoke VirtualProtect, which takes four arguments. On the aforementioned target platform, the first four parameters are passed through registers (rcx, rdx, r8, r9). In such a scenario, an attacker needs to make sure that those registers contain the correct values before VirtualProtect can be invoked. To achieve that, three different kinds of gadgets are required, namely: (i) a stack pivot gadget which points rsp to the injected data, i.e., function arguments and addresses of gadgets, (ii) gadgets to load the arguments from memory to the appropriate registers, and (iii) a gadget that calls VirtualProtect. This metric looks for gadgets that achieve these goals and distinguishes between gadgets that achieve only the required task or include other instructions. Of course, our tool reports gadgets only if the register that receives the argument is preserved, i.e., not overwritten by another instruction in the same gadget. In case the attacker wants to invoke an API that requires fewer arguments, like VirtualAlloc7 , fewer gadgets that load arguments are required. A gadget is only useful in preparing a destination register r d for use within a ROP chain if it does not destroy its value prior to returning. More concretely, consider a gadget consisting of a sequence of n instructions i 0 ; i 1 ; . . . i n-1 ; ret. If i 0 assigns the value to r d , any subsequent instruction i k with k > 0 that has r d as a target operand and falls within the data move, arithmetic, or shift and rotate categories is tagged as being potentially destructive. A second refinement step is subsequently carried out, whereby the quirks of the target architecture are taken into account. For instance, instructions that output to a 32 bit subregister are handled differently than those that output to 16 or 8 bit subregisters. This is due to the behaviour that writing to a 32 bit subregister automatically zero-extends the value to fill the entire 64 bit register [START_REF]Intel 64 and ia-32 architectures software developer's manual combined[END_REF].

In the case of exploits making use of VirtualProtect, one finds that three of the four arguments that this API call takes (namely lpAddress, the start address of the memory region whose protection level is to be changed, dsSize, the size address of the memory region whose protection level is to be changed, and lpflOldProtect, an address where the old protection level will be stored) do not need to be precise. If lpAddress is a few bytes off an attacker can take this into account, just like a slightly smaller or larger size argument. lpflOldProtect is not used by an attacker and can therefore be written to any location. Therefore, the metric only deems two instructions destructive, namely pop and mov in 64 bit or 32 bit subregisters, as they overwrite the whole register. Metric 2 allows one to assess whether a transformed binary contains gadgets typically required for an attack where the environment gives the attacker a lot of leeway.

Metric 3: Gadget Environment Setup Capabilities -Restricted

In contrast to the previous metric, this metric considers the case where an attacker is restricted in the ways in which she can inject values into memory. In particular, we consider the scenario where an attacker may only inject data and hijack the control-flow via strcpy. This complicates the direct injection of values into memory because many parameters to API calls often contain null-bytes, which terminate strings, thus requiring that the arguments to be used for correctly invoking a function such as VirtualProtect be calculated dynamically at runtime. Imagine an attacker wants to indeed invoke VirtualProtect. By taking a look at the required parameters it becomes clear that many will contain null-bytes: lpAddress should point to the payload. Depending on the memory layout, this address may contain null-bytes (e.g., in a classic stack buffer overflow vulnerability on Windows, stacks are located at very low addresses making it very likely for the address to have its leftmost bytes set to null). dwSize must not be too large, i.e., lpAddress + dwSize must include only mapped pages. The value must also not be too small, as it has to cover the memory area where the payload is injected. Typically, the value is a couple of thousand bytes or smaller, which is a value that cannot be injected directly. flNewProtect is usually set to 0x40, which cannot be injected directly because the leftmost bytes are null,and requires to be computed at runtime. lpflOldProtect will receive the old protection value, hence must point to writable memory, which may contain null-bytes. This example shows that in a scenario where the attacker is restricted, she will require various arithmetic and data-move gadgets in order to dynamically calculate parameters for API calls using gadgets.

The metric gauges the presence of gadgets that may be used to assist in evaluating values dynamically at runtime, specifically gadgets that move data between memory and registers and compute values: pop, push, add, sub, adc, dec, inc, neg, not, mov, sbb, xchg, xor. As in the case of Metric 2, a gadget is only considered if r d is preserved. Metric 3 allows one to assess whether a transformed binary contains gadgets typically required for an attack where the attacker has to make many calculations at runtime and cannot inject arbitrary data into a program.

Metric 4: Gadget Quality

The aforementioned metrics do not measure the quality of a gadget per se, rather they provide an indication whether a specific attack can succeed given a set of gadgets. This metric focuses on assessing the quality of an individual gadget, whereby a high-quality gadget is defined as one having no preconditions or side-effects on other registers or memory. An example of a precondition is that a specific register has to point to writeable memory, e.g., in the gadget pop rax ; mov [rdi+0x34fa], rsp ; ret. To be usable, rdi+0x34fa must point to writeable memory. A side-effect is, for example, that data in another register is overwritten or the stack pointer is manipulated in a way that is difficult to undo, e.g., in the gadget pop rax ; mov rcx, 0xb0adffff ; leave ; ret. This gadget overwrites the values in rcx, rsp, and rbp. To express gadget quality, a score is calculated for every gadget considered useful (see Metric 3 ). The score starts at 0 and is increased for side-effects and preconditions. Therefore, a higher score equals worse gadget quality. In the following we give a high-level overview of the two criteria we use to calculate the score for gadget quality.

Grading Instructions To measure side-effects and preconditions, the metric inspects every instruction in a gadget. It reuses the categories introduced in Section 3.1 and assigns a score to each category, which reflects how destructive the instructions in the respective category are. Table 2 summarizes the scoring system. Depending on the destination of the instruction, we apply a modifier to the originally assigned score. The metric recognizes three possible kinds of destinations: rsp, which should ideally not be modified, because it is responsible for the control flow and always needs to point to the next gadget. Therefore, modifications of rsp usually have the largest influence on the overall score of a gadget. The second possible destination is r d , the destination register in the first instruction of a gadget, for which we assume that this is also the register an exploit developer is interested in not being modified later on in the same gadget (in case a memory address is the target there is no active register; in case of an xchg instruction, both registers are active registers). Modifications of r d are generally not desirable, but, depending on the modification, can be reversible, e.g., simple arithmetic. The third possible destination is any other general purpose register, except rsp and r d , the metric considers all undesirable side effects and preconditions. Even if they do not affect rsp or r d directly, they still negatively impact the final score. 1). "RSP", "rd" and "Other" are possible targets for instructions, the stack pointer, the destination register of the first instruction of a gadget, or any of the other general purpose registers respectively. Categories not in the table generally do not affect the score, with some exceptions discussed in Section 3.4

Cat.

RSP rd Other Notes

Data move 2 1 0.5 As opposed to all other instructions in this category, push does not affect the score of a gadget, since the only side effect it has is on rsp, and changes to rsp are covered by our rsp monitoring.

Arithmetic 2 1 0.5 Arithmetic instructions that modify a register other than rsp can be taken into account by the exploit developer. E.g., if r8 should contain 0x40, and a gadget like pop r9 ; add r8, 0x10 ; ret has to be executed as the last gadget, the developer can simply make sure r8 contains the value 0x30 before invoking the last gadget. Arithmetic instructions modifying rsp are covered by our rsp monitoring.

Shift & Rotate 3 2 0.5 These instructions are handled similarly to arithmetic instructions, however, they are more difficult to take into account, which is why they increase the score more than arithmetic instructions.

In a few cases grading all instructions in one category the same does not make sense and would result in false scoring, which is the reason for the following exceptions. Exception #1: Certain instructions that modify rsp need to be treated differently. This covers all instructions where we can statically determine the offset applied to rsp. Depending on how much rsp is changed, we adjust the overall score of the gadget. The details on this are covered in the next subsection. In case it is not possible to statically determine the offset (e.g., leave or pop rsp), the overall score of the gadget is increased depending on the category of the instruction, as presented in Table 2. Exception #2: leave is the only instruction in the miscellaneous category that needs to be taken into account, as it affects rsp. This is taken care of through our rsp monitoring. Exception #3:

Remember from Section 3.1 that we do not cover all of the x86-64 instructions. This means that in very rare cases (less than 0.1%) we cannot grade a gadget because it contains an instruction which we did not categorize. We discard these gadgets from the analysis. Exception #4: If an instruction uses a dereferenced register as destination its score is increased according to the rules in Table 2, because this poses a precondition -e.g., the gadget pop r8 ; mov [rdx], 0xfffa ; ret has the precondition that rdx has to point to writable memory before the gadget can be used.

Monitoring rsp Offset Modifications to rsp need to be tracked for each gadget, as explained in the previous paragraph. A short example will make clear why this is necessary. Assume the following gadget: pop rax ; add rbx, 0x10ff ; push rcx ; ret. In this case, rsp will point to the value contained in rcx and jump to this address, which is not the injected address of the next gadget. For keeping track of the rsp offset the metric uses an SP-Score, SPS, which starts at 0, is increased for pop and decreased for push and ret n instructions. Of course, also arithmetic instructions on rsp are monitored and the respective value is added to or subtracted from SPS. When all instructions in a gadget have been analyzed and SPS is not 0 this means that rsp does not point to the next gadget, which might be problematic. Therefore, if SPS is negative, the overall score of the gadget will be increased by 2. Also, if SPS is large (more than 4 KiB) or not aligned, the score of the gadget will be increased by 1, because the former requires an attacker to be able to control more memory and the latter can be detected easily by exploit mitigation tools. If the instruction that operates on rsp takes a register and not an immediate (e.g., a add rsp, rcx), SPS is not changed but the gadget score will be increased by rules in Table 2. Metric 4 allows one to assess the overall "quality" of a set of gadgets in respect to side-effects, preconditions, and usability.

Discussion of the Metrics

We believe that metrics that measure the quality of a set of gadgets should focus on practical relevance rather than a theoretical concept such as Turing completeness [START_REF] Shacham | The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86)[END_REF]. Furthermore, they should also reflect whether real-world exploits can be constructed. Since at least Microsoft has seen a shift from classic, stack-based vulnerabilities to heap-related vulnerabilities [4], we believe that metrics should still consider both of these classes of attacks. Last but not least, the metrics should not be limited to well-defined and realistic attack scenarios, but also express overall gadget quality, i.e., side-effects and preconditions. To summarize, metrics as described above should:

-Be practical -Measure if popular current attacks are possible with a given set of gadgets -Measure if popular past attacks are possible with a given set of gadgets -Measure gadget "quality"

The proposed metrics achieve all these goals. We would like to stress that our aim is assessing whether a binary contains gadgets suitable for today's ROP attacks. Recently, attacks that use longer and more complex gadgets have been proposed by researchers [START_REF] Carlini | Rop is still dangerous: Breaking modern defenses[END_REF][START_REF] Davi | Stitching the gadgets: On the ineffectiveness of coarse-grained control-flow integrity protection[END_REF][START_REF] Göktaş | Size does matter: Why using gadget-chain length to prevent code-reuse attacks is hard[END_REF][START_REF] Göktas | Out of control: Overcoming control-flow integrity[END_REF][START_REF] Schuster | Evaluating the effectiveness of current anti-rop defenses[END_REF]. Such attacks are designed to bypass specific mitigation techniques, which are not used in the real world. Thus, in current environments, these complex attacks are cumbersome as they offer no advantage over using regular and simpler ROP gadgets, and we are not aware of any of these complex attacks being used in the wild.

Because of the lack of practical relevance, we decided not to treat gadgets potentially useful in such complex attacks differently than the other gadgets. Nevertheless, if new mitigations limiting the gadgets an attacker may use become widespread and attackers are forced to use more complex and longer gadgets and start using tools that assist in finding gadgets semantically rather than through simple pattern matching, our metrics will have to be updated to reflect this new environment. This is why we also plan to use a more abstract interpretation of gadgets and look into leveraging synergies created by combining gadgets in the future. Furthermore, we also leave an extension to jump-oriented programming (JOP) [START_REF] Bletsch | Jump-oriented programming: a new class of code-reuse attack[END_REF][START_REF] Checkoway | Return-oriented programming without returns[END_REF] for future work.

Evaluation

We have implemented the described metrics in a tool named GaLity, which takes a textfile containing gadgets as input and outputs the metrics we described in Section 3. We demonstrate that it is both practical and useful by applying it to binaries that are compiled to use MPX [START_REF] Ramakesavan | Intel memory protection extensions (intel mpx) enabling guide[END_REF], Intel's latest mitigation technique against runtime exploits. MPX introduces new registers that contain the lower and upper bound of a pointer, and instructions that operate on those registers. This enables compilers to emit additional instructions (MPX and non-MPX) that tracks the sizes of buffers and accesses to those buffers at runtime, which can prevent buffer overflows. On processors which do not support MPX, MPX instructions execute as nop, making MPX compatible with older CPUs, but leaving those binaries unprotected by MPX. Given this observation one thus must wonder if the increased code size and thus increased availability of gadgets might actually decrease a binary's security on such systems. We then compare the results obtained by applying GaLity to binaries compiled with MPX support with the results obtained by applying GaLity to the same binaries compiled without MPX support, and determine which binaries contain more helpful gadgets for an attacker according to our metrics.

Implementation

We wrote GaLity in C#. GaLity takes a simple text file that contains gadgets as input and parses it in four passes, which correlate to the four metrics described in the previous section. While doing everything in one pass is certainly possible, we decided to use several passes, as this increases code readability, and performance was no issue (even large sets of gadgets containing hundreds of thousands of gadgets can be analyzed in less than 10 seconds on an Intel Core 2 Duo with 4 GiB RAM). Since current ROP attacks use rather simple gadgets we only reconstruct the semantic we require for our metrics. For example, GaLity recognizes the differences between instructions outputting to 64 bit, 32 bit, 16 bit, or 8 bit (sub)registers and treats them accordingly, but does not recognize that many instructions manipulate CPU flags. Knowledge about this would be required when utilizing more complex gadgets that use conditional branches. However, for current real-world attacks, the simpler but less error-prone approach is sufficient.

We looked into using an intermediate representation (IR) which makes side effects explicit, as this would allow more precise grading. However, we discovered that, as today's attacks use simple gadgets, there are few side effects that are relevant in our scenarios. Therefore, we leave designing an IR tailored to the very specific requirements of measuring gadget quality, that (1) can be reused and (2) recognizes more side effects, for future work.

Setup

To discover gadgets and write them to a file we used ROPgadget 5.4 8 , with a maximum gadget length of 15. This might sound like a very high number, however, we did not want to risk potentially missing some useful gadgets. Also, our metrics ensure that gadgets that do not preserve r d are discarded, i.e., not considered in the results, and gadgets that have many side effects have a bad score. Also, for this specific case study we decided to consider duplicate gadgets and not just unique gadgets, because if an important gadget exists several times in a binary, this binary is more attractive to an attacker than a binary which contains only one copy of that gadget. This matters, for example, in a scenario where a patch (security-related or not) or any other program modification removes said gadget. Furthermore, taking duplicate gadgets into account helps us measure, if the additional gadgets introduced by MPX are copies of useless or useful gadgets.

We compiled programs taken from SPEC2006, using Intel's latest GCC release with MPX support at the time of writing (5.0.0). 9 We decided to use the SPEC suite because it covers a wide range of application types, and present parts of real programs. MPX is still new and not integrated too well in build chains, which made compiling any program a challenge. However, we got the following eight programs to work properly: 401.bzip2, 403.gcc, 435.gromacs, 456.hmmer, 458.sjeng, 464.h264ref, 473.astar, 482.sphinx3. We compiled all binaries four times, with and without MPX and with and without optimizations (-O2). However, for our evaluation we only considered optimized binaries as this reflects real-world binaries.

Results

Table 3. Results for Metrics 2, 3, and 4. Columns rcx, rdx, r8 and r9 denote the number of gadgets which load a value in the respective register, column pivot denotes the number of stack pivot gadgets. The first number denotes the number of gadgets without side-effects, the second number the number of gadgets with side-effects. Column call denotes the number of gadgets usable for indirect calls. First of all, we noticed that MPX has a big influence on file size. With no optimizations, an MPX binary is, on average, almost 3 times as large as a non-MPX binary. With optimization level 2, which we used throughout our experiments, an MPX binary is still, on average, 86% larger compared to a non-MPX binary. We noticed that, while the file size increases by a factor of almost two, the number of gadgets does not increase in the same way, MPX binaries contain, on average, only 23% more gadgets than non-MPX binaries. This is because the number of gadgets is directly related to the number of ret instructions in a binary. MPX does not add many new functions but rather makes existing functions longer, therefore only few intended new ret instructions appear. Unintended ret instructions [START_REF] Roemer | Return-oriented programming: Systems, languages, and applications[END_REF] might appear in some cases, however, since the new opcodes introduced by MPX do not contain a ret opcode, the possibility for this is rather low.

Analyzing the increase or decrease of gadgets for each category due to MPX, illustrated in Figure 1, shows that most categories gain gadgets. Arithmetic gadgets, which are helpful to an attacker, increase in both number and diversity.

Data-move gadgets grow in numbers, but do not change a lot in respect to diversity. An interesting observation is that NOP-gadgets increase drastically, which is presumably due to the fact that the new MPX instructions are interpreted as multi-byte NOPs on hardware that does not support MPX. The categories flag, string and floating-point have a high standard deviation, indicating that changes in these categories are very application-specific. Gadgets in the miscellaneous category decrease both in diversity and number. Despite the large increase of nop gadgets, the overall distribution of gadgets remains roughly the same, as Figure 2 shows. Overall we conclude that MPX binaries contain more gadgets in categories helpful to an attacker. This figure shows the average growth of gadgets for each category due to MPX across all eight applications. The blue bar represents the increase considering only unique gadgets, while the red bar represents the total increase of gadgets, i.e., also duplicate gadgets. We use the information about how the number of unique gadgets changes to infer if and how gadget variety is affected by a program transformation.

Next, we are interested in the two attack scenarios, i.e., Metrics 2 and 3. Regarding Metric 2, there is no big difference in the availability of gadgets. Gadgets that load arguments in r8 or r9 are rare in both MPX and non-MPX binaries, and sometimes the MPX binary and sometimes the non-MPX binary contains some. Regarding Metric 3, the number of useful gadgets increases in every binary and on average by 17%, making MPX binaries a much more attractive target to attackers. We summarize the results in Table 3. Lastly, we determine overall gadget quality using Metric 4. In all eight binaries, the MPX versions contain more gadgets of high quality, i.e., with fewer side-effects and preconditions, as the last column of Table 3 shows. By taking all four results into consideration we come to the conclusion, that binaries compiled with MPX support are favourable for an attacker. Metric 1 shows an overall increase of gadgets in useful categories, further confirmed by Metric 3, which also shows that the additional gadgets in those categories are useful in practice. Metric 2 gives no indication that MPX or non-MPX binaries contain more of the required gadgets. Metric 4 gives the indication that MPX binaries tend to have more gadgets of higher quality, making them easier to use for an attacker.

Related Work

To the best of our knowledge, no previous work has been done on the topic of designing a metric to measure the quality of a set of gadgets, even though the metrics currently used to measure CFI strength are insufficient, exactly because gadget quality is not expressed by those metrics. Due to this lack of related work, we introduce the metrics that are currently used to evaluate CFI implementations, and discuss gadgets required for carrying out attacks against CFI.

Zhang et al. [START_REF] Zhang | Control flow integrity for cots binaries[END_REF] propose using AIR which denotes how many gadgets are removed, because they are not acceptable targets of indirect branches. However, AIR does not take into account the quality of the remaining gadgets. Payer et al. [START_REF] Payer | Fine-grained control-flow integrity through binary hardening[END_REF] propose DAIR, which works similarly to AIR but is dynamic, hence varies during program execution. Tice at al. [START_REF] Tice | Enforcing forward-edge control-flow integrity in gcc & llvm[END_REF] propose forward-edge AIR (fAIR), which is computed like AIR, but takes into account only forward-edge indirect control transfers, i.e., calls and jumps. All of the above metrics are limited to CFI though, and do not consider the quality of the remaining gadgets.

Carlini et al. [START_REF] Carlini | Control-flow bending: On the effectiveness of control-flow integrity[END_REF] discuss the effectiveness of CFI implementations against ROP attacks and propose what they call a basic exploitation test (BET). BET consists of three generalized attack scenarios, namely arbitrary code execution, confined code execution and information leakage. They use a minimal program that allows exploitation, apply several CFI implementations, and evaluate, which of the described attack scenarios could be achieved. However, this process was done by a human, hence dependant on skill and knowledge of the exploit developer. Therefore, it can also not be used for mass-analyzing binaries.

In 2014 and 2015 many attacks targeting various CFI implementations, e.g., kBouncer [START_REF] Pappas | Transparent rop exploit mitigation using indirect branch tracing[END_REF], ROPecker [START_REF] Cheng | Ropecker: A generic and practical approach for defending against rop attacks[END_REF], or CFI for COTS [START_REF] Zhang | Control flow integrity for cots binaries[END_REF] have been published. As CFI places tight restrictions on indirect control-flow transfers, hence also gadgets, those attacks often incorporate gadgets that would rarely used in real attacks. E.g., Carlini and Wagner [START_REF] Carlini | Rop is still dangerous: Breaking modern defenses[END_REF], Davi et al. [START_REF] Davi | Stitching the gadgets: On the ineffectiveness of coarse-grained control-flow integrity protection[END_REF], and Göktaş et al. [START_REF] Göktaş | Size does matter: Why using gadget-chain length to prevent code-reuse attacks is hard[END_REF] discovered that long gadgets with few side effects are suitable for breaking heuristics-based mitigations. Such gadgets should consist of at least 20 instructions, preserve as many registers as possible, have few side-effects, and easily fulfillable preconditions. Gadgets of this length are generally not useful in today's attacks, and therefore GaLity does not treat them any different than other gadgets. Another kind of gadget commonly used in these attacks is an LBR-flushing gadget [START_REF] Carlini | Rop is still dangerous: Breaking modern defenses[END_REF][START_REF] Schuster | Evaluating the effectiveness of current anti-rop defenses[END_REF]. Recent CPUs have special registers which can be configured to store the addresses of up to the 16 most recent taken indirect branches [START_REF]Intel 64 and ia-32 architectures software developer's manual combined[END_REF], which is a feature kBouncer [START_REF] Pappas | Transparent rop exploit mitigation using indirect branch tracing[END_REF] and ROPecker [START_REF] Cheng | Ropecker: A generic and practical approach for defending against rop attacks[END_REF] use. When certain, critical APIs are invoked, the LBR is inspected and, depending on whether the control-flow appears legitimate or not, an exception is raised. LBR-flushing gadgets are gadgets that naturally contain many indirect branches, present in the regular control flow, e.g., functions that call lots of sub-functions. By using such a gadget, the LBR is filled with legitimate addresses and there is no trace of irregular control flow, i.e., ROP, in the LBR.

Q [START_REF] Schwartz | Q: Exploit hardening made easy[END_REF] allows exploit developers to write a target program in the high-level language QooL and automatically builds a ROP chain that uses only gadgets from a provided binary. However, Q handles gadgets with side effects, which we call preconditions in this paper, very conservatively and discards such gadgets, potentially removing a large number of useful gadgets. Homescu et al. [START_REF] Homescu | Microgadgets: Size does matter in turing-complete return-oriented programming[END_REF] present a Turing-complete set of gadgets, using only gadgets that are 3 byte or shorter. They find that all required gadgets appear very frequently in regular Linux binaries.

Lastly, there are many tools that assist exploit developers by finding and sorting gadgets, but none of them take into account the quality of gadgets. Some of these tools also attempt to automatically build a ROP exploit for one predefined scenario e.g., ROPgadget 10 , Mona.py 11 , or ropper 12 , however, from our experience they are not very sophisticated and often fail, even if the necessary gadgets are available.

Conclusion

Return-Oriented Programming forms the cornerstone of many contemporary exploitation techniques, yet its viability hinges on the availability of useful gadgets. Program transformations, including exploit mitigation techniques, often do not take into consideration their impact on the quality and number of gadgets that they introduce into the binary to which they are applied. Evaluations usually concentrate on the security gained, but not the security that might be lost due to a set of gadgets that is now favourable for an attacker than in the original, unmodified binary. This work addresses this issue and allows researchers to consider this important aspect, by developing a set of metrics that, by combining concrete attack scenarios and measuring overall gadget quality, cover a wide range of possible exploit scenarios. We implemented the described metrics in a tool called GaLity, and applied it to binaries compiled with MPX, a new buffer overflow prevention technique introduced by Intel. Our results show that MPX provides gadgets of higher quality, and also a favourable set of gadgets in a concrete attack scenario.

  Fig.1. This figure shows the average growth of gadgets for each category due to MPX across all eight applications. The blue bar represents the increase considering only unique gadgets, while the red bar represents the total increase of gadgets, i.e., also duplicate gadgets. We use the information about how the number of unique gadgets changes to infer if and how gadget variety is affected by a program transformation.

Fig. 2 .

 2 Fig. 2. This figure shows the average distribution of gadgets across all eight applications. The blue bar represents the non-MPX binaries, while the red bar represents the MPX binaries.

Table 1 .

 1 Gadget Categories

	Category	Included Instructions
	Data move	pop, push, mov, xchg, lea, cmov, movabs
	Arithmetic	add, sub, inc, dec, sbb, adc, mul, div, imul, idiv, xor,
		neg, not 6
	Logic	cmp, and, or, test
	Control flow call, sysenter, enter, int, jmp, je, jne, jo, jp, js,
		lcall, ljmp, jg, jge, ja, jae, jb, jbe, jl, jle, jno, jnp,
		jns, loop, jrcxz
	Shift & Rotate shl, shr, sar, sal, ror, rol, rcr, rcl
	Setting flags xlatb, std, stc, lahf, cwde, cmc, cld, clc, cdq
	String	stosd, stosb, scas, salc, sahf, lods, movs
	Floating point divps, mulps, movups, movaps, addps, rcpss, sqrtss, maxps,
		minps, andps, orps, xorps, cmpps, vsubpd, vpsubsb, vmulss,
		vminsd, ucomiss, subss, subps, subsd, divss, addss,
		addsd, cvtpi2ps, cvtps2pd, cvtsd2ss, cvtsi2sd, cvtsi2ss,
		cvtss2sd, mulsd, mulss, fmul, fdiv, fcomp, fadd
	Misc	wait, set, leave
	MMX	pxor, movd, movq
	NOP	nop
	RET	ret

Table 2 .

 2 Rules for grading instructions. Category describes the category of the instruction (see Table

  These numbers are required for computing Metric 2. Column useful denotes the number of useful gadgets, calculated by Metric 3. Column Q denotes the number of gadgets with a score of 1 or lower, calculated by Metric 4.

				Metric 2			Metric 3 Metric 4
	Program	rcx	rdx	r8	r9	pivot	call useful Q
	h264ref no MPX 4 / 29	1 / 8	1 / 9 0 / 0 0 / 453 62	6,056	3,749
	h264ref MPX	7 / 29	0 / 23	1 / 3 0 / 1 0 / 666 91	7,546	4,906
	gromacs no MPX 228 / 320 39 / 135 0 / 2 0 / 0 0 / 1071 84	10,823	6,563
	gromacs MPX	228 / 418 36 / 141 0 / 7 0 / 1 0 / 1214 155 13,002	8,170
	hmmer no MPX 6 / 24	3 / 27	0 / 3 0 / 0 0 / 509 33	5,539	3,303
	hmmer MPX	8 / 21	4 / 19	0 / 2 0 / 0 0 / 469 39	6,188	3,952
	gcc no MPX	4 / 71	2 / 219 0 / 14 0 / 8 6 / 5295 588 50,766	32,949
	gcc MPX	2 / 52	4 / 71	0 / 9 0 / 4 0 / 4337 763 59,522	39,342
	sphinx3 no MPX 2 / 14	0 / 11	0 / 0 0 / 0 0 / 230 29	3,189	1,964
	sphinx3 MPX	1 / 11	0 / 7	0 / 0 0 / 0 1 / 251 52	3,484	2,323
	sjeng no MPX	1 / 3	0 / 3	0 / 0 0 / 1 0 / 122 72	1,444	983
	sjeng MPX	1 / 4	0 / 5	0 / 0 0 / 0 0 / 137 76	1,982	1,414
	astar no MPX	1 / 4	0 / 4	0 / 0 0 / 0 0 / 122 11	1,009	584
	astar MPX	0 / 5	0 / 2	0 / 0 0 / 0 0 / 140 12	1,203	698
	bzip2 no MPX	0 / 1	0 / 1	0 / 0 0 / 0 0 / 99 13	790	466
	bzip2 MPX	0 / 1	0 / 1	0 / 0 0 / 0 0 / 112 16	987	605

https://msdn.microsoft.com/en-us/library/windows/desktop/aa366898%28v=vs.85%29.aspx

https://msdn.microsoft.com/en-us/library/windows/hardware/ff561499%28v=vs.85%29.aspx

It might appear peculiar that xor, neg, not are in the arithmetic category -however, this is how exploit developers often use these instructions. Since using nullbytes is sometimes prohibited by the environment, writing the negated or xor-ed value in memory, loading it to a register and then using the same operation on it again is used to bypass this restriction.

https://msdn.microsoft.com/en-us/library/windows/desktop/aa366887%28v=vs.85%29.aspx

https://github.com/JonathanSalwan/ROPgadget

https://software.intel.com/en-us/articles/intel-software-development-emulator

Acknowledgements

We want to express our thanks to the anonymous reviewers for their valuable comments. In particular, we want to thank our shepherd, Mathias Payer, who helped us give this paper its final form. This work was supported by the BMBF within EC SPRIDE, by the Hessian LOEWE excellence initiative within CASED, by the DFG Collaborative Research Center CROSSING, by the DFG Priority Program 1496 Reliably Secure Software Systems, and the project IN-TERFLOW.

conducted Eric Bodden was at Fraunhofer SIT and TU Darmstadt.


H Hein

L Feklistova

Free vibrations of non-uniform and axially functionally graded beams using Haar wavelets

Vibrations of non-uniform and functionally graded (FG) beams with various boundary conditions and varying cross-sections are investigated using the Euler-Bernoulli theory and Haar matrices. It is assumed that the cross-section and material properties vary along the beam in the axial direction. The system of the governing equations is transformed with the aid of a set of simplest wavelets. To validate the present results, the non-homogeneity of the beams is discussed in detail and the calculated frequencies are compared with those of the existing literature. The results show that the Haar wavelet approach is capable of calculating frequencies for the beams with different shapes, rigidity, mass density, small or large translational and rotational boundary coefficients. The advantage of the novel approach consists in its simplicity, accuracy and swiftness.

Introduction

In contemporary engineering conditions, the requirements for structural materials and their properties are becoming more stringent. This is particularly true for the materials which are used in constructional elements or assembly units and are utilized in extremely severe environment or adverse exploitation. Nevertheless, traditional means for improving characteristics and performance of natural materials are depleted. Therefore, an increasing interest in composite materials and the materials with gradients in composition is evident. The tendency is also provoked by economical aspects: extraction and processing of natural resources is limited and expensive.

FG materials withstand high temperatures and resist corrosion. On account of comparatively good fracture toughness, FG materials are less exposed to delamination or cracking in comparison to uniform or homogeneous beams; therefore, FG materials have been under important consideration among engineers in recent decades. A detailed overview of the advanced materials, their development, elemental composition, microstructure, properties, design and application are described in [START_REF] Feklistova | Modeling and analysis of functionally graded materials and structures[END_REF] by Byrd. A more comprehensive research on thermoelastic behaviour of FG structures was first conducted by Chakraborty et al. in 2003 yet. Static, free vibrations and wave propagation were investigated by the beam element approach which required an exact solution of the static part of the governing differential equations [START_REF] Chakraborty | A new beam finite element for the analysis of functionally graded materials[END_REF]. Aydogdu and Taskin studied free vibrations of simply supported FG beams with the aid of classical beam theory, parabolic and exponential shear deformation beam theories. The governing equations were found by the Navier type solution [START_REF] Aydogdu | Free vibration analysis of functionally graded beams with simply supported edges[END_REF]. A unified approach for analysing both static and dynamic behaviour of FG beams was proposed by Li extending the Timoshenko beam theory [START_REF] Li | A unified approach for analyzing static and dynamic behaviour of functionally graded Timoshenko and Euler-Bernoulli beams[END_REF]. A fundamental frequency analysis using different higher-order beam theories was carried out by Simsek [START_REF] Simsek | Fundamental frequency analysis of functionally graded beams by using different higher-order beam theories[END_REF]. In 2010, Alshorbagy et al. suggested FEM for calculating dynamic characteristics of FG beams with material graduation in axially or transversally through the thickness based on the power law [START_REF] Alshorbagy | Free vibration characteristics of a functionally graded beam by finite element method[END_REF]. The same method was applied by Shahna et al. for stability analysis of FG tapered Timoshenko beam [START_REF] Shahba | Free vibration and stability analysis of axially functionally graded tapered Timoshenko beams with classical and non-classical boundary conditions[END_REF]. Xiang and Yang studied forced vibrations of a three-layer laminated FG Timoshenko beam with arbitrary end supports and varying thickness due to the applied heat [START_REF] Xiang | Free and forced vibration of a laminated FGM Timoshenko beam of variable thickness under heat conduction[END_REF]. Recently Simsek and Kocatürk studied dynamic behaviour of FG simply-supported beams under a concentrated moving harmonic load. The approach was based on Lagrange's equations [START_REF] Simsek | Free and forced vibration of a functionally graded beam subjected to a concentrated moving harmonic load[END_REF]. Bending and vibration of cylindrical beams with arbitrary radial non-homogeneity were investigated by Huang and Li [START_REF] Huang | Bending and vibration of circular cylindrical beams with arbitrary radial nonhomogeneity[END_REF]. A dynamic system with a moving mass was broadly studied by Simsek in [START_REF] Simsek | Vibration analysis of a functionally graded beam under a moving mass by using different beam theories[END_REF][START_REF] Simsek | Non-linear vibration analysis of a functionally graded Timoshenko beam under action of a moving harmonic load[END_REF], and Khalili et al. [START_REF] Khalili | A mixed Ritz-DQ method for forced vibration of functionally graded beams carrying moving loads[END_REF]. A new approach for calculating free vibration of FG beams with non-uniform cross-section area and varying physical properties along its longitude was proposed by Huang and Li [START_REF] Huang | A new approach for free vibration of axially functionally graded beams with non-uniform cross-section[END_REF] last year. The approach was based on the Fredholm integration equation.

The analytical method for studying free vibrations of FG beams was provided by Sina et al. [START_REF] Sina | An analytical method for free vibration analysis of functionally graded beams[END_REF] and Mahi et al. [START_REF] Mahi | An analytical method for temperaturedependent free vibration analysis of functionally graded beams with general boundary conditions[END_REF] only a few years ago. The equation of deflection was derived applying Hamilton's principle. The Galerkin method was employed to analyse free vibration of sandwich beams with FG core in [START_REF] Amirani | Free vibration analysis of sandwich beam with FG core using the element free Galerkin method[END_REF].

Despite the variety of methods and approaches for analytical and computational analysis of non-uniform and FG beams, no simple and fast solutions applicable for both free and forced vibrations in such beams with different boundary conditions and varying cross-section area were proposed. Only few solutions are found for the studies on the axially FG beams. Hereof, the purpose of the present work is to introduce the Haar wavelet approach for calculating natural frequencies in non-uniform and FG beams. The paper is organized in five sections. Section 2 describes integration of Haar wavelets. In Section 3, the problem and the solution are stated. Various numerical examples can be found in Section 4. The main conclusions are drawn in Section 5.

Integration of Haar wavelets

The Haar wavelet is one of the simplest wavelets which is discontinuous and resembles a step function. In other words, the Haar wavelets belong to the special class of discrete orthonormal wavelets. The other wavelets generated from the same mother wavelet form a basis whose elements are orthonormal to each other and are normalized to unit length. This property allows each wavelet coefficient to be computed independently of other wavelets. The Haar wavelet family for ξ ∈ [0, 1] is defined as follows: (1) , ξ (2) ], -1 for ξ ∈ [ξ (2) , ξ (3) ], 0 elsewhere.

h i (ξ ) =    1 for ξ ∈ [ξ
(

In (1), notations

ξ (1) = k m , ξ (2)
= k + 0.5 m , ξ (3)
= k + 1 m (2)
are introduced. Integer m = 2 j (j = 0, 1, . . . , J) is the factor of scale; k = 0, 1, . . . , m -1 is the factor of delay. Integer J determines the maximal level of resolution. Index i in (1) is calculated as i = m + k + 1; the minimal value for i is one (if j = 0, then m = 1, k = 0); the maximal value of i is 2M, which is 2 J+1 . If index i is equal to one, the corresponding scaling function

is h 1 (ξ ) = 1 if ξ ∈ [0, 1],
and h 1 (ξ ) = 0 elsewhere. In [START_REF] Hsiao | State analysis of time-varying singular nonlinear systems via Haar wavelets[END_REF], the Haar coefficient matrix H (2M×2M) (i, l) = h i (ξ l ) is introduced; the collocation points are defined as:

ξ l = l -0.5 2M , l = 1, 2, . . . , 2M. (3)
For further studies, the integrals of the wavelets

p α,i (ξ ) = ∫ ξ 0 p α i-1,i (ξ ) dξ (4)
are required. In (4), p 0,i (ξ ) = h i (ξ ). These integrals are calculated analytically [START_REF] Lepik | Numerical solution of differential equations using Haar wavelets[END_REF]. In case i = 1, the integral of the wavelet is p α,1 (ξ ) = ξ α /α!, and in case i > 1 is

p α,i (ξ ) =                         
0 for ξ < ξ (1) , ) , ξ (2) ], 2) , ξ (3) ],

1 α!  ξ - k m  α for ξ ∈ [ξ (1
1 α! [ ξ - k m  α -2(ξ -ξ (2) ) α ] for ξ ∈ [ξ (
1 α! [ ξ - k m  α -2(ξ -ξ (2) ) α + (ξ -ξ (3) ) α ]
for ξ > ξ (3) .

(

) 5
Values p α,i (0) and p α,i (1) should be calculated in order to satisfy the boundary conditions. Evaluating integrals (5) in the collocation points, the following form could be obtained

P (α) (i, l) = p α,i (ξ l ), (6)
where P (α) is a 2M ×2M matrix. It should be noted that calculations of matrices H(i, l) and P (α) (i, l) must be carried out only once.

Problem statement and method of solution

Consider an axially graded Euler-Bernoulli beam with a variable cross-section of length L. In the present study, it is assumed that the material properties and cross-section of the beam vary continuously along the length. Introducing the quantities:

ξ = x L , k 4 = ρ 0 A 0 ω 2 L 4 E 0 I 0 , (7)
the equation of motion for transverse vibrations is given by

d 2 dξ 2 [ E(ξ )I(ξ ) d 2 W (ξ ) dξ 2 ] -k 4 m(ξ )W (ξ ) = 0, ξ ∈ [0, 1], (8)
where

W (ξ ) is the transverse deflection, m(ξ ) = ρ(ξ )A(ξ ) is the mass at position ξ , E(ξ )I(ξ ) = D(ξ ) is the bending stiffness; ρ(ξ )
is the mass density of the beam material, E(ξ ) is the Young's modulus, A(ξ ) is the cross-section area and I(ξ ) is the moment of inertia at ξ . In [START_REF] Shahba | Free vibration and stability analysis of axially functionally graded tapered Timoshenko beams with classical and non-classical boundary conditions[END_REF], k is the dimensionless natural frequency, and ρ 0 , A 0 , E 0 , I 0 denote the values of ρ, A, E, I at ξ = 0, respectively.

In the present study, it is assumed that functions E(ξ ) and I(ξ ) have derivatives up to the second order. From ( 8), it yields that

d 4 W (ξ ) dξ 4 E(ξ )I(ξ ) + 2 d 3 W (ξ ) dξ 3 [ dE(ξ ) dξ I(ξ ) + dI(ξ ) dξ E(ξ ) ] + d 2 W (ξ ) dξ 2 [ d 2 E(ξ ) dξ 2 I(ξ ) + 2 dE(ξ ) dξ dI(ξ ) dξ + d 2 I(ξ ) dξ 2 E(ξ ) ] -k 4 W (ξ )ρ(ξ )A(ξ ) = 0, ξ ∈ [0, 1]. (9)
For a general case, the solution of ( 9) is not available. According to [START_REF] Hsiao | State analysis of time-varying singular nonlinear systems via Haar wavelets[END_REF][START_REF] Lepik | Numerical solution of differential equations using Haar wavelets[END_REF], a highest-order derivative is expanded into the Haar series instead of solving the differential equation. Therefore, it is assumed that the fourth derivative of the solution ( 9) is sought in the following form:

W IV (ξ ) = 2M - i=1 a i h i (ξ ), (10)
where a i are unknown wavelet coefficients. Integrating [START_REF] Huang | Bending and vibration of circular cylindrical beams with arbitrary radial nonhomogeneity[END_REF] four times and taking into account (4) and ( 5), we obtain

W ′′′ (ξ ) = 2M - i=1 a i p 1,i (ξ ) + W ′′′ (0), W ′′ (ξ ) = 2M - i=1 a i p 2,i (ξ ) + W ′′′ (0)ξ + W ′′ (0), W ′ (ξ ) = 2M - i=1 a i p 3,i (ξ ) + 1 2 W ′′′ (0)ξ 2 + W ′′ (0)ξ + W ′ (0), W (ξ ) = 2M - i=1 a i p 4,i (ξ ) + 1 6 W ′′′ (0)ξ 3 + 1 2 W ′′ (0)ξ 2 + W ′ (0)ξ + W (0). (11)
In [START_REF] Simsek | Vibration analysis of a functionally graded beam under a moving mass by using different beam theories[END_REF], quantities W (0), W ′ (0), W ′′ (0), W ′′′ (0) can be evaluated from the boundary conditions. In the present work, the following boundary conditions are considered: (i) Cantilever beams (CF)

In this case, one end ξ = 0 is clamped, while the other end ξ = 1 is free. The boundary conditions for the beam are W (0) = W ′ (0) = 0, W ′′ (1) = W ′′′ (1) = 0 and the system is derived from [START_REF] Simsek | Vibration analysis of a functionally graded beam under a moving mass by using different beam theories[END_REF] as follows:

2M - i=1 a i p 1,i (1) + W ′′′ (0) = 0, 2M - i=1 a i p 2,i (1) + W ′′′ (0) + W ′′ (0) = 0. (12)
Evaluating the system, W ′′ (0) and W ′′′ (0) are obtained

W ′′ (0) = 2M - i=1 a i q 1,i , W ′′′ (0) = - 2M - i=1 a i p 1,i (1)
, [START_REF] Khalili | A mixed Ritz-DQ method for forced vibration of functionally graded beams carrying moving loads[END_REF] where q 1,i = p 1,i (1) -p 2,i (1). In this case, the mode shape W is described by the following equation:

W (ξ ) = 2M - i=1 a i [ p 4,i (ξ ) - 1 6 p 1,i (1)ξ 3 + 1 2 q 1,i ξ 2 ] . (14)
(ii) Simply supported beams (SS) In the case of simply supported beam, the boundary conditions

are W (0) = W ′′ (0) = 0, W (1) = W ′′ (1) = 0 and the system is 2M - i=1 a i p 2,i (1)
+ W ′′′ (0) = 0, 2M - i=1 a i p 4,i (1)
+ 1 6 W ′′′ (0) + W ′ (0) = 0. (15)
From [START_REF] Sina | An analytical method for free vibration analysis of functionally graded beams[END_REF] we get

W ′′′ (0) = - 2M - i=1 a i p 2,i (1)
,

W ′ (0) = 1 6 2M - i=1 a i q 2,i , W (ξ ) = 2M - i=1 a i [ p 4,i (ξ ) - 1 6 p 2,i (1)ξ 3 + 1 6 q 2,i ξ ] , (16)
where

q 2,i = p 2,i (1) -6p 4,i (1).
(iii) Clamped beams (CC)

Satisfying the boundary conditions,

W (0) = W ′ (0) = 0, W (1) = W ′ (1) = 0 for the clamped-clamped beams one could get W ′′′ (0) = 6 2M - i=1 a i q 3,i , W ′′ (0) = 2M - i=1 a i q 4,i , W (ξ ) = 2M - i=1 a i [ p 4,i (ξ ) + q 3,i ξ 3 + 1 2 q 4,i ξ 2 ] , (17)
where q 3,i = 2p 4,i (1) -p 3,i (1) and q 4,i = 2p 3,i (1) -6p 4,i (1).

(iiii) Clamped-pinned (CP) beams

As a representative, it is assumed that one end ξ = 0 is clamped or fixed and the other end ξ = 1 is pinned or simply supported. Thus, the corresponding boundary conditions are W (0) = W ′ (0) = 0, W (1) = W ′′ (1) = 0. In this case from [START_REF] Simsek | Vibration analysis of a functionally graded beam under a moving mass by using different beam theories[END_REF] one could get

W ′′′ (0) = 2M - i=1 a i q 5,i , W ′′ (0) = 2M i=1 a i q 6,i , (ξ ) = 2M - i=1 a i [ p 4,i (ξ ) + 1 6 q 5,i ξ 3 + 1 2 q 6,i ξ 2 ] , (18)
where q 5,i = 3p 4,i (1) -3 2 p 2,i (1) and q 6,i = -q 5,i -p 2,i (1).

For the illustration of the method, consider a case of the cantilever beam. Next the notation is introduced as follows:

a(:)H(:, l) = 2M - i=1 a i h i (ξ l ). (19)
Substituting [START_REF] Huang | Bending and vibration of circular cylindrical beams with arbitrary radial nonhomogeneity[END_REF], [START_REF] Simsek | Vibration analysis of a functionally graded beam under a moving mass by using different beam theories[END_REF] and ( 13) into ( 9), taking into account [START_REF] Lepik | Numerical solution of differential equations using Haar wavelets[END_REF] and discretizing the results by taking ξ → ξ l , the governing system is derived

a(:)  H(:, l)U 1 (l) + 2  P (1) (:, l) -P (1) (:, 1)E(l)  U 2 (l)
+  P (2) (:, l) -P (1) (:, 1)ξ l E(l) + q 1 (:)ξ 2 l E(l)  U 3 (l) -k 4 [ P (4) (:, l) - 1 6
P (1) (:, 1)ξ 3 l E(l) + 1 2 q 1 (:)ξ 2 l E(l) ] U 4 (l)  , l = 1, . . . , 2M, (20)
where

U 1 (l) = E(ξ l )I(ξ l ), U 2 (l) = E ′ (ξ l )I(ξ l ) + E(ξ l )I ′ (ξ l ), U 3 (l) = E ′′ (ξ l )I(ξ l ) + 2E ′ (ξ l )I ′ (ξ l ) + E(ξ l )I ′′ (ξ l ), U 4 (l) = ρ(ξ l )A(ξ l ) (21)
and E(l) is a unit row vector. The system (20) is linear and homogeneous with regard to a i and contains frequency parameter ω. For deriving a nontrivial solution, the determinant of system (20) must be zero. According to this requirement, the values for ω are evaluated.

Numerical examples

A comparison of the results for uniform homogeneous beams

Consider a homogeneous cantilever with a uniform crosssection. In this case, D = EI and m = ρA are constants. The comparisons of the exact [START_REF] Karnovsky | Formulas for structural dynamics[END_REF] and calculated dimensionless natural frequencies (DNF) k for different levels of resolution J are presented in Table 1. It is seen in the table that high accuracy is obtained using a small number of grid points.

Beams with non-uniform cross-section and elastic end constraints

The suggested approach of the Haar wavelets was applied to the wedge beam with a rectangular cross-section and clampedfree ends. Due to the shape, the breadth and the height of the beam were described by the formulae:

h(ξ ) = h 0 [1 + (α h -1)ξ ] , b(ξ ) = b 0 [1 + (α b -1)ξ ] , (22)
where α b stands for the ratio between the breadths at the beginning and at the end of the beam; α h is the ratio between the heights respectively. In Table 2, the first dimensionless natural frequencies k 2 for the wedge beam with α b = 1, α h = α and the cone beam with α b = α h = α are presented. The results calculated by Hsu et al. [START_REF] Hsu | Free vibration of non-uniform EulerBernoulli beams with general elastically end constraints using Adomian modified decomposition method[END_REF] are given in columns two and four. The level of resolution was taken as J = 5. According to the results, the Haar wavelets approach works accurately with insignificant errors in the cases of simple wedge beam models.

Next, consider a non-uniform beam with elastic end constants. The boundary conditions in the presence of translational and rotational spring constants at ξ = 0 are presented as [START_REF] Hsu | Free vibration of non-uniform EulerBernoulli beams with general elastically end constraints using Adomian modified decomposition method[END_REF]:

d dξ [ I(ξ ) d 2 w(ξ ) dξ 2 ] + k tl w(ξ ) = 0, (23)
I(ξ ) d 2 w(ξ ) dξ 2 -k rl dw(ξ ) dξ = 0. (24)
In ( 23) and ( 24), the non-dimensional translational and rotational spring coefficients k t and k r are

k tl = K TL L 3 EI 0 , k rl = K RL L EI 0 . ( 25
)
The boundary conditions on the right end ξ = 1 are defined analogically. The first two natural frequencies with α b = α h = 1.4, fixed rotational spring constraints k rr = k rl = 0 and varying translational spring constraints are presented in Table 3.

The results are compared with Hsu's [START_REF] Hsu | Free vibration of non-uniform EulerBernoulli beams with general elastically end constraints using Adomian modified decomposition method[END_REF] calculations.

It is important to note that the provided method of Haar wavelets is capable of calculating different frequencies for both small and large translational coefficients. The results are precise, however, an attempt to improve the accuracy was done on account of resolution. The model and conditions were remained the same as in the previous example, but the resolution was increased from five to seven.

As it can be seen from Table 4, the accuracy of calculations grows with the growth of resolution. However, according to Lepik [START_REF] Lepik | Numerical solution of differential equations using Haar wavelets[END_REF], it is so only to a certain extend of the resolution.

Table 4

The third DNF k 2 for the beam with translational constraints and k rr = k rl = 0 with different resolutions.

k tl = k tr [START_REF] Hsu | Free vibration of non-uniform EulerBernoulli beams with general elastically end constraints using Adomian modified decomposition method[END_REF] Present The first DNF k 2 for the beam with varying translational and fixed rotational end constraints (J = 5). The first three DNF k 2 for the beam with parabolic-taper width and linear-taper height (J = 5).

J = 5 Present J = 6 Present J = 7 0.
k tl = k tr k rr = 0.5, k rl = 1 k rr = 1, k rl = 0.
α n = 1 n = 2 n = 3 Present [22] Present [ 22] Present [22] 0.1 5

Table 7

The first DNF of the cantilever with parabolic thickness (rectangular and circular cross-section) versus the dimensionless coordinate of the fixed end (J = 5).

ξ 1

Cross-section

Rectangular Circular [START_REF] Caruntu | Dynamic modal characteristics of transverse vibrations of cantilevers of parabolic thickness[END_REF] Present [START_REF] Caruntu | Dynamic modal characteristics of transverse vibrations of cantilevers of parabolic thickness[END_REF] Present -0.7 The Haar wavelet approach was also applied to the beams with varying translational and fixed rotational end constraints (k rr = 0.5, k rl = 1) with α b = 2 and α h = 1 (Table 5).

The study on the frequencies proves that there is slight dependence between the rotational constraints and the crosssection area. The influence can be observed with the growth of the translational constraint value. Now consider a truncated at α tapered beam [START_REF] Zhou | The free vibration of a type of tapered beams[END_REF] with parabolic-taper width b(ξ ) = b 0 √ ξ and linear-taper height h(ξ ) = h 0 ξ . The first three DNF for boundary conditions (on the left end k rl = k tl = 0 and on the right end k rr → ∞, k tr → ∞) with J = 5 are presented in Table 6. The calculated results correspond well to the previous works. Finally, examine the Haar wavelet approach on the cantilever with parabolic thickness versus the dimensionless coordinate of the fixed end (h = h 0 (1-ξ 2 )) and the cantilever with circular cross-section and parabolic thickness. The results of the calculations and comparison are provided in Table 7. The calculated results correspond to the previous research.

Table 8

The first DNF of axially graded beam the gradient parameter (J = 5).

Uniform beams with variable flexural rigidity and mass density

Consider a uniform beam with axial non-homogeneity. Assume that bending stiffness and mass density vary according to the following equation:

Q (ξ ) =    Q 0  1 - e βξ -1 e β -1  + Q 1 e βξ -1 e β -1 , β ̸ = 0, Q 0 (1 -ξ ) + Q 1 ξ , β = 0. (26)
In ( 26), Q 0 and Q 1 stand for the corresponding material properties at the ends ξ = 0, ξ = 1 respectively, and β is the gradient.

The material is chosen to consist of aluminium and zirconia as follows [START_REF] Huang | A new approach for free vibration of axially functionally graded beams with non-uniform cross-section[END_REF] Al: E 0 = 70 ρ 0 = 2702 kg/m 3 ,

ZrO 2 : E 1 = 200 GPa, ρ 1 = 5700 kg/m 3 . ( 27
)
The first natural frequencies for the functionally graded beams with different boundary conditions are calculated and presented in Table 8.

Beams with non-uniform cross-section, variable flexural rigidity and mass density

Next, consider a functionally graded beam with non-uniform cross-section. Assume that the cross-section of the beam has constant width and linearly varying height, i.e. A/A 0 = 1 + βξ , I/I 0 = (1 + βξ ) 3 . The Young's modulus and the mass density are considered as trigonometric functions:

E(ξ ) = E 0 [1 + γ cos(π ξ )] , ρ(ξ ) = ρ 0 [1 + δ cos(π ξ )] , (28)
where |γ | < 1 and |δ| < 1 are parameters. In Table 9, the calculated first natural frequencies for δ = 4γ and different values of β are presented. The natural frequencies of the tapered cantilever are sensitive to parameter γ .

Non-homogeneous beams with variable flexural rigidity, mass density and elastic end constraints

Here we consider the cases of axially FG beams with unusual boundary conditions. Let the flexural rigidity and mass density of the beam vary in the following form: 23)-( 25). In Table 10, the first natural frequencies are presented for the case of fixed translational and rotational spring constants at the right end (k rr = k tr = 1) and variable constants at the left end.

D(ξ ) = D 0 [1 + α cos(π ξ )] , ρ(ξ ) = ρ 0 [1 + β cos(π ξ )] , (29)

Non-homogeneous beams with variable flexural rigidity, mass density, elastic end constraints and intermediate rigid support

Finally, the present method can also be applied for beams with additional intermediate constraints. Let us consider an axially FG beam with variable flexural rigidity and mass density varying according to the Eq. (29). The beam has rotational and translational flexible ends and an additional rigid support at ξ = γ . In the presence of the rigid support, the condition is

W (γ ) = 0. ( 30
)
According to [START_REF] Hsiao | State analysis of time-varying singular nonlinear systems via Haar wavelets[END_REF], the Eq. (30) takes the form:

W (γ ) = 2M - i=1 a i [ p 4,i (γ ) + 1 6 q 5,i γ 3 + 1 2 q 6,i γ 2 ] . (31)
In Table 11, the calculated first natural frequencies for the fixed translational and rotational spring constants k rr = k tr = k rl = k tl = 1, varying α = β and different values of γ are presented.

It can be seen in Table 11 that in the case of symmetric boundary conditions, the natural frequencies at the right end and left end are not the same. This is explained by non-symmetric FG material distribution in the beam.

Conclusions

The Haar wavelet approach was presented to solve free vibrations of non-uniform Euler-Bernoulli beams with continuously varying flexural rigidity and mass density. A numerical method was developed for general nonlinear functions. The obtained results were compared with those given in [START_REF] Huang | A new approach for free vibration of axially functionally graded beams with non-uniform cross-section[END_REF][START_REF] Hsu | Free vibration of non-uniform EulerBernoulli beams with general elastically end constraints using Adomian modified decomposition method[END_REF][START_REF] Zhou | The free vibration of a type of tapered beams[END_REF][START_REF] Caruntu | Dynamic modal characteristics of transverse vibrations of cantilevers of parabolic thickness[END_REF]. The benefits of the Haar wavelet approach are its simplicity and sparse matrices of presentation. The computational time is therefore comparatively small. High accuracy is obtained even with a small number of grid points. The method is easily applicable for systems with discontinuities and works effectively in the case of non-linearity.

Table 1

 1 The first four DNF k n for uniform cantilever beams.

	n	[20]	J = 2	J = 3	J = 4	J = 5	J = 6
	1	1.8751	1.8783	1.8759	1.8753	1.8752	1.8751
	2	4.6941	4.7342	4.7040	4.6966	4.6948	4.6943
	3	7.8548	7.9991	7.8899	7.8635	7.8570	7.8553
	4	10.9956	11.3505	11.0804	11.0165	11.0008	10.9969

Table 2

 2 The first DNF k 2 for the wedge and cone cantilever.

	α	Wedge beam		Cone beam
		[21]	Present	[21]	Present
	0.1	4.63074	4.6305	7.20500	7.2055
	0.4	3.93428	3.9343	5.00906	5.0088
	0.6	3.73708	3.7373	4.31879	4.3189
	0.7	3.66675	3.6670	4.06694	4.0671
	0.9	3.55870	3.5589	3.67371	3.6739

Table 3

 3 The first two DNF k 2 for a beam with translational constraints and k rr = k rl = 0.

	k tl = k tr	n = 1		n = 2
		[21]	Present	[21]	Present
	0.001	0.21656	0.2166	0.31795	0.3180
	0.01	0.38510	0.3851	0.5639	0.5654
	0.1	0.68462	0.6846	1.00528	1.0053
	1	1.21404	1.2140	1.78509	1.7851
	10	2.10096	2.1009	3.13023	3.1303
	100	3.07241	3.0723	5.06670	5.0668
	1000	3.37553	3.3754	6.56963	6.5697

Table 5

 5

	001	5.19178	5.1927	5.1920	5.1918
	0.01	5.19196	5.1929	5.1922	5.1920
	0.1	5.19381	5.1948	5.1940	5.1939
	1	5.21223	5.2132	5.2125	5.2123
	10	5.39376	5.3948	5.3940	5.3938
	100	6.71152	6.7125	6.7118	6.7116
	1000	9.28876	9.2894	9.2889	9.2888

Table 6

 6

	5

Table 9

 9 The first DNF of the axially graded tapered cantilever with variable Young's modulus and mass density (J = 5).

	β	S-S				C-P
		Present	[14]	Present	[14]	Present	[14]
	-10	11.4481	11.4532	24.0269	24.0576	16.3837	16.4775
	-3	11.2422	11.2443	23.9384	23.9456	16.0307	16.0219
	0	10.8660	10.8663	24.3749	24.3752	15.8729	15.8734
	3	10.3670	10.3669	24.9371	24.9375	15.7171	15.7171
	10	9.9366	9.9358	24.8080	24.7949	15.4930	15.4956
	γ	β
		-0.2	-0.1		0.0	0.1	0.2
	-0.2	2.6468	2.6051	2.5691	2.5378	2.5102
	-0.1	3.0553	3.0103	2.9716	2.9378	2.9082
	0.0	3.6085	3.5589	3.5162	3.4789	3.4460
	0.1	4.4492	4.3922	4.3430	4.2999	4.2618
	0.2	6.0214	5.9518	5.8909	5.8372	5.7893

Table 10

 10 The first DNF for beams the with variable flexural rigidity, mass density and elastic end constraints (J = 5, k rr = k tr = 1).

	α = β	k rl = k tl
		1.0	2.0	3.0	4.0	5.0
	-0.2	1.4408	2.0732	2.5756	3.0206	3.4420
	-0.15	1.4120	2.0309	2.5191	2.9473	3.3462
	0.15	1.2950	1.8632	2.3030	2.6794	3.0176
	0.2	1.2818	1.8446	2.2795	2.6510	2.9842

Table 11

 11 The first DNF for beams with variable flexural rigidity, elastic end constraints and intermediate rigid support (J = 5, k rr = k tr = k rl = k tl = 1). |α| < 1 and |β| < 1 are parameters. The conditions insure that D(ξ ) and ρ(ξ ) are positive. The ends of the beam are fixed by elastic spring supports. The boundary conditions in the presence of rotational and translational spring constants are given by Eqs. (

	α = β	γ
		0.1	0.3	0.5	0.7	0.9
	-0.2	1.8902	2.8150	4.0124	3.9385	3.2176
	-0.15	1.9120	2.8620	4.0277	3.8784	3.1657
	0.15	2.0578	3.1553	4.0527	3.5405	2.8874
	0.2	2.0851	3.2077	4.0475	3.4879	2.8455

where

Acknowledgement

The financial support from the Estonian Foundation under Grant 8830 is acknowledged.


C H Romine

B W Peyton

COMPUTING CONNECTION COEFFICIENTS OF COMPACTLY SUPPORTED WAVELETS ON BOUNDED INTERVALS

Daubechies wavelet basis functions have many properties that make them desirable as a basis for a Galerkin approach to solving PDEs: they are orthogonal, with compact support, and their connection coe cients can be computed. The method developed by Latto et al. 6] to compute connection coe cients does not provide the correct inner product near the endpoints of a bounded interval, making the implementation of boundary conditions problematic. Moreover, the highly oscillatory nature of the wavelet basis functions makes standard numerical quadrature of integrals near the boundary impractical. We extend the method of Latto et al. to construct and solve a linear system of equations whose solution provides the exact computation of the integrals at the boundaries. As a consequence, we provide the correct inner product for wavelet basis functions on a bounded interval.

Introduction

Wavelets are receiving increased attention not only as a mechanism for constructing lter banks or compressing data, but as a natural basis for multilevel schemes for solving PDEs. Several papers in recent years have described the use of wavelet basis functions in solving PDEs, for example Amaratunga Wavelet basis functions have many properties that make them desirable as a basis for a Galerkin approach to solving PDEs: they are orthonormal, with compact support, and their connection coe cients (that is, integrals of products of basis functions, with or without derivatives) can be computed 6]. However, these properties rely on the assumption that the PDE is periodic in the computational domain (which is equivalent to the assumption that the domain is unbounded), and do not all carry over when the domain of the PDE is bounded. Orthogonality, for example, is lost when the basis functions are truncated at a boundary because the domain of integration is a nite interval.

Approaches that assume periodicity complicate the treatment of boundary conditions for PDEs in a nite domain. In a Galerkin formulation, the discretized form of the equation involves connection coe cients on bounded intervals. We call these proper connection coe cients, since they involve proper integrals. The usual connection coe cients computed in Latto et al. with a doubly in nite domain of integration will be called improper connection coe cients. Note that when the support of the integrand lies entirely within the interior of the computational domain, corresponding proper and improper connection coe cients are equal.

The highly oscillatory nature of wavelet basis functions makes standard numerical quadrature for computing connection coe cients impractical. Latto et al. circumvent this problem for improper connection coe cients by exploiting properties of the wavelet basis functions to derive a linear system of equations whose solution has as its components the exact improper connection coe cients.

As far as we know, no one has previously devised a method for computing proper connection coe cients. As a result, the natural inner product for Galerkin solution of boundary value problems has been unavailable, and researchers have been restricted to more indirect means of resolving the boundary, e.g., the capacitance matrix method of The paper is organized as follows. Section 2 presents background and notation. Section 3 describes our technique for computing proper connection coe cients. In section 4, we use our technique to solve a simple one-dimensional di erential equation with Dirichlet boundary conditions. Section 5 provides a few concluding remarks.

Background and Notation

The rst step in developing a basis is to de ne the underlying scale function. The scale function satis es the recursive dilation equation

(x) = N?1 X k=0 a k (2x ? k)
where N is an even integer no smaller than two and fa k g are the lter coe cients. Daubechies 5] imposed conditions on the lter coe cients so that the resulting scale functions with Daubechies number N are di erentiable and the resulting bases are orthonormal and have N 2 ? 1 vanishing moments (i.e., can be used to exactly represent polynomials of degree N 2 ? 1). We will use all these important properties in our derivations. Throughout we will use the Daubechies scale functions D4 (N = 4), D6 (N = 6), D8 (N = 8), etc. A graph of the scale function for N = 6 is given in Figure 2.1. Also, to improve our notation we will let k (x) := (x ? k):

For more about Daubechies wavelets and their properties consult Daubechies 5], Strang 10] The wavelet-Galerkin method for solving PDEs on an unbounded domain produces improper connection coe cients as terms in its equations. If we use the notation (n) := d n dx n , then the two-term improper connection coe cients are de ned (as in Latto, et al.) as

d 1 d 2 j := Z 1 ?1 (d 1 ) (x) (d 2 ) j (x)dx
and three-term improper connection coe cients are de ned by

d 1 d 2 d 3 j;k := Z 1 ?1 (d 1 ) (x) (d 2 ) j (x) (d 3 ) k (x)dx:
Only the nonzero coe cients are computed: in the two-term case 2 ? N j N ? 2, and in the three term case 2 ? N j; k N ? 2 and jj ? kj N ? 2.

There is no loss of generality in xing the shift on the rst term at zero because

d 1 d 2 i;j = Z 1 ?1 (d 1 ) i (x) (d 2 ) j (x)dx = Z 1 ?1 (d 1 ) (x) (d 2 ) j?i (x)dx and d 1 d 2 d 3 i;j;k := Z 1 ?1 (d 1 ) i (x) (d 2 ) j (x) (d 3 ) k (x)dx = Z 1 ?1 (d 1 ) (x) (d 2 ) j?i (x) (d 3 ) k?i (x)dx:
The scale function is the foundation upon which the basis is constructed. Each member of the basis at resolution m is of the form m;k (x) := 2 m=2 (2 m x ? k) = 2 m=2 k (2 m x):

Each member of the basis is thus a scaled, dilated, and translated version of the underlying scale function.

The wavelet-Galerkin method for solving PDEs on a bounded domain produces proper connection coe cients as terms in its equations. If we assume (in one dimension) that the interval of computation is 0, 1], then for the resolution m basis, the proper two-term connection coe cients will be of the form

Z 1 0 (d 1 ) m;i (x) (d 2 ) m;j (x)dx:
Since the resolution m basis functions are simply scaled, translated, and dilated versions of the underlying scale function, it is enough to compute proper connec-tion coe cients of the form:

? d 1 d 2 i;j := Z N?1 0 (d 1 ) i (x) (d 2 ) j (x)dx
The limits of integration 0 and N ? 1 are a natural choice to ensure that the support of no basis function in the integrand crosses both limits of integration. Once the proper connection coe cients ? d 1 d 2 i;j have been tabulated, all connection coe cients at resolution m can be derived. For example, if the computational domain is 0, 1] then assuming 2 m > N ? 1,

Z 1 0 (d 1 ) m;?1 (d 2 ) m;?2 dx = Z 2 m 0 (d 1 ) (y + 1) (d 2 ) (y + 2)dy; (where y = 2 m x) = Z N?1 0 (d 1 ) (y + 1) (d 2 ) (y + 2)dy = ? d 1 d 2
?1;?2 ; since the support of (d 1 ) (y + 1) (d 2 ) (y + 2) is -1, N ? 3]. Similarly,

Z 1 0 (d 1 )
m;2 m ?1

(d 2 )
m;2 m ?2 dx = Z N?1 ?2 m +(N ?1) (d 1 ) (y ? (N ? 2)) (d 2 ) (y ? (N ? 3))dy; (where y = 2 m x ? 2 m + (N ? 1)) = Z N?1 0 (d 1 ) (y ? (N ? 2)) (d 2 ) (y ? (N ? 3))dy = ? d 1 d 2 N?2;N?3 ;

since the support of (d 1 ) (y ?(N ?2)) (d 2 ) (y ?(N ?3)) is N ? 2, 2N ? 4]. Note that if the support of the integrand lies entirely within the computational domain, the corresponding proper and improper connection coe cients are equal; that is, ? d 1 d 2 i;j = d 1 d 2 j?i (using the notation in Latto, et al.). Two basis functions for a proper two-term connection coe cient that involves a boundary are illustrated in Figure 2.2. Three-term proper connection coe cients are de ned by

? d 1 d 2 d 3 i;j;k := Z N?1 0 (d 1 ) i (x) (d 2 ) j (x) (d 3 ) k (x)dx
and similar de nitions apply for higher numbers of terms. In the two-term case we can restrict our attention to proper connection coe cients for which either 2 ? N i; j ?1, or 1 i; j N ? 2. All others are either zero, or are equivalent to some improper connection coe cient. Similarly, for the three-term case we restrict our attention to proper connection coe cients for which either 2 ? N i; j; k ?1, or 1 i; j; k N ? 2. Note that the integrals can no longer be shifted to reduce the total number of distinct proper connection coe cients by assigning a zero shift to the rst term.

Moreover, the truncation of a basis function is not arbitrary, but occurs at one of the dyadic points (i=2 m ) in the given resolution. Equivalently, the truncation occurs at an integer value at the resolution of the scale function. The interval of integration ( 0, N ? 1]) combined with all possible integer shifts cover all possible truncations at integer points of shifted products of the scale function.

Computing Proper Connection Coe cients

We illustrate our technique by computing the three-term proper connection coefcients. The same technique is easily applied to the two-term proper connection coe cients. Our approach is based on suitable modi cations of the scaling equations, moment equations, and the normalization equation, described in Latto, et al. 6].

Scaling equations

We begin this section by deriving a relationship among the unknowns ? d 1 d 2 d 3 i;j;k that will eliminate half of them. We note rst that the support of (d) i is i, i + (N ? 1)]. Then for 1 i; j; k N ? 2 we have:

? We now derive the scaling equations. If 2 ? N i ?1, then since i (x) = (x ? i) = N?1 X p=0 a p (2x ? (2i + p))

we have

(d 1 ) i (x) = 2 d 1 N?1 X p=0 a p (d 1 ) (2x ? (2i + p)):
Similarly, with 2 ? N j; k ?1 we have

(d 2 ) j (x) = 2 d 2 N?1 X q=0 a q (d 2 ) (2x ? (2j + q)) and (d 3 ) k (x) = 2 d 3 N?1 X r=0 a r (d 3 ) (2x ? (2k + r)): Hence, ? d 1 d 2 d 3 i;j;k = 2 d N?1 X p=0 N?1 X q=0 N?1 X r=0
a p a q a r Z N?1 0 (d 1 ) (2x ? (2i + p)) (d 2 ) (2x ? (2j + q)) (d 3 ) (2x ? (2k + r))dx;

(where d = d 1 + d 2 + d 3 ), or

? d 1 d 2 d 3 i;j;k = 2 d N?1 X p=0 N?1 X q=0 N?1 X r=0
a p a q a r Z 2N ?2 0 (d 1 ) (y ? (2i + p)) (d 2 ) (y ? (2j + q)) (d 3 ) (y ? (2k + r))dy;

or

? d 1 d 2 d 3 i;j;k = 2 d N?1 X p=0 N?1 X q=0 N?1 X r=0
a p a q a r ( Z N?1 0 (d 1 ) (y ? (2i + p)) (d 2 ) (y ? (2j + q)) (d 3 ) (y ? (2k + r))dy + Z N?1 0 (d 1 ) (y ? (2i + p ? (N ? 1))) (d 2 ) (y ? (2j + q ? (N ? 1))) (d 3 ) (y ? (2k + r ? (N ? 1)))dy); or

? d 1 d 2 d 3 i;j;k = 2 d?1 N?1 X p=0 N?1 X q=0 N?1 X r=0
a p a q a r (3.2) (? d 1 d 2 d 3 2i+p;2j+q;2k+r + ? d 1 d 2 d 3 2i+p?(N ?1);2j+q?(N?1);2k+r?(N?1) )

Note that some of the terms on the right hand side of (3.2) are equal to improper connection coe cients, since the entire support of some of the integrands lies within the bounds of integration. These terms are known (thanks to Latto, et. al.), and hence can be moved to the other side. Moreover, we exploit the identity (3.1) to eliminate the unknowns corresponding to 1 i; j; k N ? 2, producing a matrix equation of the form:

(I ? 2 d?1 A)? d 1 d 2 d 3 = R (3.3)
in (N ?2) 2 unknowns, where R is a vector accumulating the known values in the sum (3.2). A similar treatment holds for the proper connection coe cients ? d 1 d 2 d 3 i;j;k with 1 i; j; k N ?2, though as noted, these can be computed from (3.1) once the values of ? i;j;k for ?(N ? 2) i; j; k ?1 are known.

The linear system (3.3) is inhomogeneous; however, the coe cient matrix I ? 2 d?1 A in (3.3) may not be of full rank. Indeed, our observations of the spectrum of I ? 2 d?1 A indicate that it has a zero eigenvalue with multiplicity d, which would imply that the rank de ciency of the coe cient matrix in (3.3) is d.

Moment Equations

If the coe cient matrix in (3.3) is singular, we augment the matrix by adding d 1 + d 2 + d 3 moment equations to the linear system in (3.3), which are derived as follows (see Latto, et al. 6]). We assume that the Daubechies number is su ciently high that we have maxfd 1 ; d 2 ; d 3 g vanishing moments. Then for each q < d 1 there exist coe cients fM q i g such that

x q = 1 X i=?1 M q i i (x):
The set fM q i g are called the moments of and its translates, and the reader is referred to Latto et al. [START_REF] Daubechies | Orthonormal bases of compactly supported wavelets[END_REF]] for details on how to compute them.

On the closed interval 0, N ? 1], we have the identity

x q = N?2 X i=2?N M q i i (x); Again, some of the entries on the right hand side of (3.6) are equal to improper connection coe cients, and hence can be moved to the other side. Others can be eliminated via the identity (3.1). This provides d 1 further (inhomogeneous) linear equations in the unknowns ? d 1 d 2 d 3 i;j;k , one for each value of q. Similarly, we can derive d 2 further moment equations 0 = N?2 X j=2?N M q j ? d 1 d 2 d 3 i;j;k :

and d 3 moment equations 0 = N?2 X k=2?N M q k ? d 1 d 2 d 3 i;j;k :

Normalization Equation

The rectangular system of linear equations derived from the scaling equations and moment equations for the improper connection coe cients is homogeneous, and hence require a nonhomogeneous equation to \normalize" the solution 6].

The rectangular system of equations described above for the proper connection coe cients is already nonhomogeneous; however, the matrix may still be rankde cient. We now derive the normalization equation for the proper connection coe cients, and include it in the system of equations. We conjecture (and our tests indicate) that the rectangular system of equations containing the scaling equations, the moment equations and the normalization equation is of full rank, and therefore the nonhomogeneous linear system has a unique solution.

If we assume that the basis functions have maxfd 1 ; d 2 ; d 3 g vanishing moments, then we have the following:

x

d 1 = 1 X i=?1 M d 1 i i : Di erentiating d 1 times, we obtain d 1 ! = 1 X i=?1 M d 1 i d 1 i :
Including only those basis functions whose support intersects the interval 0, N ? 1],

One approach to imposing Dirichlet boundary conditions in a Galerkin formulation is to replace two of the rows in (4.3) with the two linear equations derived from the two boundary conditions, preserving a square coe cient matrix. An alternative, and the approach we chose, is to append the two boundary equations to the matrix, and solve the resulting rectangular system.

Our test problem is u xx = ?4 2 sin(2 x); u(0) = 1; u(1) = 2 whose exact solution is u = sin(2 x)+x+1. Figure 4.1 is a graph of the error as a function of resolution on a log-log scale for Daubechies number N = 6. The slope of the resulting line demonstrates cubic convergence with increase in resolution. We have demonstrated a technique for deriving a linear system whose solution is the set of proper connection coe cients needed to compute the natural inner product on bounded intervals. The ability to compute proper connection coe cients provides a natural mechanism for imposing boundary conditions. We exhibited a simple one-dimensional test problem that illustrates the use of proper connection coe cients for PDE's on bounded domains with Dirichlet boundary conditions. We showed that convergence of the solution using Daubechies D6 basis functions was cubic with increasing resolution.

The wavelet-Galerkin approach for solving PDEs has su ered from the inability to properly set PDE problems on bounded domains and to impose boundary conditions in a straightforward way. We have shown that this drawback can be eliminated when the proper connection coe cients can be computed. Moreover, these proper connection coe cients can also be used to compute the proper wavelet connection coe cients arising from a multiresolution analysis of PDEs.

  et al. 1, 2], Bacry et al. 3], Qian and Weiss 8], and Restrepo and Leaf 9].

Figure 2

 2 Figure 2.1: The scale function for Daubechies number N = 6.

Figure 2 . 2 :

 22 Figure 2.2: Basis functions for a proper connection coe cient

(3. 4 )

 4 where we have included all terms in the sum whose support intersects the given interval. Di erentiating[START_REF] Amaratunga | Wavelet-Galerkin solutions for one dimensional partial di erential equations[END_REF]

  Wavelet-Galerkin Approximation, N=6

Figure 4 . 1 :

 41 Figure 4.1: Illustration of convergence rate

  Proskurowski and Widlund 7]; see Amaratunga, et al. 2] and Qian and Weiss 8]. Motivated by the need to extend methods for resolving boundary conditions in a new and natural direction, we address the problem of computing proper connection coe cients. We adapt the methology of Latto et al., exploiting the properties of the wavelet basis functions to derive two linear systems whose solutions have as their components the exact proper connection coe cients.

Acknowledgements

We are grateful to John Drake and Bill Lawkins for our introduction to wavelets for solving PDEs and for many helpful conversations.

(3.9)

Multiplying equations (3.7), (3.8) and (3.9) together, and integrating over 0, N ? 1] we obtain

Again, some of the terms in (3.10) are either known, or can be eliminated via the identity (3.1). We provide tables of proper connection coe cients in the appendix for the two cases (N = 6, d 1 = 0, d 2 = 2) and (N = 6, d 1 = 1, d 2 = 0 and d 3 = 0), the same two cases provided by Latto et al. in 6]. Although the values of ? d 1 d 2 d 3 i;j;k for 1 i; j; k N ? 2 can be computed indirectly using the identity (3.1) we compute both tables of proper connection coe cients independently and use 3.1 as an accuracy check. For the tables provided in the appendix, the identity (3.1) is satis ed to within approximately 10 ?15 .

Since the multiresolution wavelet basis f m;k g is de ned in terms of the scale function, the proper connection coe cients derived here can also be used for multiresolution analysis. Speci cally, if the multiresolution wavelet basis is used in a Galerkin formulation for the solution of PDEs, the necessary wavelet connection coe cients can be computed directly from the proper connection coe cients given here.

Results

In this section, we demonstrate the applicability of proper connection coe cients by solving a simple one-dimensional di erential equation on the bounded domain 0, 1]. We use the 1-D Poisson problem u xx ? f = 0; The Galerkin approach approximates u and f with linear combinations of basis functions: u X i u i m;i ; and f X i f i m;i :

The left hand side of (4.1) is now approximated by u xx ? f X u i 00 m;i ?

In general, these approximations will not satisfy the di erential equation exactly;

however, we can nd the orthogonal projection onto the space spanned by f j g by ensuring that (4.2) is orthogonal to each so-called \test function" j . That is, we de ne an inner product h m;i ; j i = Z 1 0 m;i j dx and solve the following linear equations for the unknowns u i : X u i h 00 i ; j i ? f i h i ; j i = 0:

If the test functions and the basis functions coincide (the choice for Galerkin test functions), the linear system will have a square coe cient matrix.

A. Tables of Proper Connection Coe cients j = ?4 ?3 ?2 ?1 i = ?4 -0.00038529074526 -0.00386035962858 0.01423373435011 -0.01534522683341 ?3 -0.00573652265285 -0.09863430110098 0.33947817016054 -0.35475020354956 ?2 0.02181281253982 0.33904059142268 -1.37506723951242 1.77076145459755 ?1 -0.06519463330387 -0.90634814610999 4.01066114451254 -5.67304693652727

Table A.1: Table of ? 02 i;j := R N?1 0 i (x) (2) j (x)dx for N = 6 i = ?4 k = ?4 ?3 ?2 ?1 j = ?4 -0.00000002530682 -0.00000068992720 0.00000306963647 -0.00001055718019 ?3 -0.00000068992720 -0.00002337260152 0.00010672670559 -0.00037345654025 ?2 0.00000306963647 0.00010672670559 -0.00048341871765 0.00168470385967 ?1 -0.00001055718019 -0.00037345654025 0.00168470385967 -0.00585973132675 i = ?3 k = ?4 ?3 ?2 ?1 j = ?4 -0.00000032826247 -0.00000752895920 0.00003138211915 -0.00010322628046 ?3 -0.00000752895920 -0.00028821307592 0.00136993458233 -0.00488523455350 ?2 0.00003138211915 0.00136993458233 -0.00714394837814 0.02677812707263 ?1 -0.00010322628046 -0.00488523455350 0.02677812707263 -0.10280576120976 i = ?2 k = ?4 ?3 ?2 ?1 j = ?4 0.00000077866139 0.00001753615235 -0.00007347449696 0.00024195517558 ?3 0.00001753615235 0.00076195056336 -0.00351927324338 0.01231761138106 ?2 -0.00007347449696 -0.00351927324338 0.01914653677375 -0.07281061430283 ?1 0.00024195517558 0.01231761138106 -0.07281061430283 0.28689868099225 i = ?1 k = ?4 ?3 ?2 ?1 j = ?4 -0.00000194921939 -0.00004221923539 0.00017491280955 -0.00057333107231 ?3 -0.00004221923539 -0.00190418619493 0.00818703214249 -0.02741471871558 ?2 0.00017491280955 0.00818703214249 -0.04587567964823 0.17576474944728 ?1 -0.00057333107231 -0.02741471871558 0.17576474944728 -0.70948149953627