投递文章
投稿指南
Request for Comments: 4465 M. West
Category: Informational Siemens/Roke Manor Research
June 2006
Signaling Compression (SigComp) Torture Tests
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2006).
Abstract
This document provides a set of "torture tests" for implementers of
the Signaling Compression (SigComp) protocol. The torture tests
check each of the SigComp Universal Decompressor Virtual Machine
instructions in turn, focusing in particular on the boundary and
error cases that are not generally encountered when running
well-behaved compression algorithms. Tests are also provided for
other SigComp entities such as the dispatcher and the state handler.
Table of Contents
1. Introduction ....................................................3
2. Torture Tests for UDVM ..........................................4
2.1. Bit Manipulation ...........................................4
2.2. Arithmetic .................................................5
2.3. Sorting ....................................................7
2.4. SHA-1 ......................................................8
2.5. LOAD and MULTILOAD .........................................9
2.6. COPY ......................................................11
2.7. COPY-LITERAL and COPY-OFFSET ..............................12
2.8. MEMSET ....................................................14
2.9. CRC .......................................................15
2.10. INPUT-BITS ...............................................16
2.11. INPUT-HUFFMAN ............................................17
2.12. INPUT-BYTES ..............................................19
2.13. Stack Manipulation .......................................20
2.14. Program Flow .............................................22
2.15. State Creation ...........................................23
2.16. STATE-ACCESS .............................................26
3. Torture Tests for Dispatcher ...................................28
3.1. Useful Values .............................................28
3.2. Cycles Checking ...........................................31
3.3. Message-based Transport ...................................32
3.4. Stream-based Transport ....................................34
3.5. Input Past the End of a Message ...........................36
4. Torture Tests for State Handler ................................38
4.1. SigComp Feedback Mechanism ................................38
4.2. State Memory Management ...................................41
4.3. Multiple Compartments .....................................44
4.4. Accessing RFC 3485 State ..................................49
4.5. Bytecode State Creation ...................................50
5. Security Considerations ........................................53
6. Acknowledgements ...............................................53
7. Normative References ...........................................53
Appendix A. UDVM Bytecode for the Torture Tests ..................54
A.1. Instructions ..............................................54
A.1.1. Bit Manipulation ...................................54
A.1.2. Arithmetic .........................................55
A.1.3. Sorting ............................................55
A.1.4. SHA-1 ..............................................56
A.1.5. LOAD and MULTILOAD .................................56
A.1.6. COPY ...............................................56
A.1.7. COPY-LITERAL and COPY-OFFSET .......................57
A.1.8. MEMSET .............................................57
A.1.9. CRC ................................................57
A.1.10. INPUT-BITS ........................................57
A.1.11. INPUT-HUFFMAN .....................................58
A.1.12. INPUT-BYTES .......................................58
A.1.13. Stack Manipulation ................................58
A.1.14. Program Flow ......................................59
A.1.15. State Creation ....................................59
A.1.16. STATE-ACCESS ......................................60
A.2. Dispatcher Tests ..........................................61
A.2.1. Useful Values ......................................61
A.2.2. Cycles Checking ...................................62
A.2.3. Message-based Transport ............................62
A.2.4. Stream-based Transport .............................62
A.2.5. Input Past the End of a Message ....................63
A.3. State Handler Tests .......................................64
A.3.1. SigComp Feedback Mechanism .........................64
A.3.2. State Memory Management ............................64
A.3.3. Multiple Compartments ..............................65
A.3.4. Accessing RFC 3485 State ...........................66
A.3.5. Bytecode State Creation ............................66
1. Introduction
This document provides a set of "torture tests" for implementers of
the SigComp protocol, RFC 3320 [2]. The idea behind SigComp is to
standardize a Universal Decompressor Virtual Machine (UDVM) that can
be programmed to understand the output of many well-known compressors
including DEFLATE and LZW. The bytecode for the chosen decompressor
is uploaded to the UDVM as part of the SigComp message flow.
The SigComp User’s Guide [1] gives examples of a number of different
algorithms that can be used by the SigComp protocol. However, the
bytecode for the corresponding decompressors is relatively well
behaved and does not test the boundary and error cases that may
potentially be exploited by malicious SigComp messages.
This document is divided into a number of sections, each containing a
piece of code designed to test a particular function of one of the
SigComp entities (UDVM, dispatcher, and state handler). The specific
boundary and error cases tested by the bytecode are also listed, as
are the output the code should produce and the number of UDVM cycles
that should be used.
Each test runs in the SigComp minimum decompression memory size (that
is, 2K), within the minimum number of cycles per bit (that is, 16)
and in tests where state is stored 2K state memory size is needed.
2. Torture Tests for UDVM
The following sections each provide code to test one or more UDVM
instructions. In the interests of readability, the code is given
using the SigComp assembly language: a description of how to convert
this assembly code into UDVM bytecode can be found in the SigComp
User’s Guide [1].
The raw UDVM bytecode for each torture test is given in Appendix A.
Each section also lists the number of UDVM cycles required to execute
the code. Note that this figure only takes into account the cost of
executing each UDVM instruction (in particular, it ignores the fact
that the UDVM can gain extra cycles as a result of inputting more
data).
2.1. Bit Manipulation
This section gives assembly code to test the AND, OR, NOT, LSHIFT,
and RSHIFT instructions. When the instructions have a multitype
operand, the code tests the case where the multitype contains a fixed
integer value, and the case where it contains a memory address at
which the 2-byte operand value can be found. In addition, the code
is designed to test that the following boundary cases have been
correctly implemented:
1. The instructions overwrite themselves with the result of the bit
manipulation operation, in which case execution continues
normally.
2. The LSHIFT or RSHIFT instructions shift bits beyond the 2-byte
boundary, in which case the bits must be discarded.
3. The UDVM registers byte_copy_left and byte_copy_right are used to
store the results of the bit manipulation operations. Since no
byte copying is taking place, these registers should behave in
exactly the same manner as ordinary UDVM memory addresses.
at (64)
:a pad (2)
:b pad (2)
at (128)
JUMP (start) ; Jump to address 255
at (255)
:start
; The multitypes are values
; $start = 448 (first 2 bytes of AND instr)
AND ($start, 21845) ; 448 & 21845 = 320 = 0x0140
OR ($a, 42) ; 0 | 42 = 42 = 0x002a
NOT ($b) ; ~0 = 65535 = 0xffff
LSHIFT ($a, 3) ; 42 << 3 = 336 = 0x0150
RSHIFT ($b, 65535) ; 65535 >> 65535 = 0 = 0x0000
OUTPUT (64, 4) ; Output 0x0150 0000
; The multitypes are references
AND ($a, $start) ; 336 & 320 = 320 = 0x0140
OR ($a, $a) ; 320 | 320 = 320 = 0x0140
NOT ($a) ; ~320 = 65215 = 0xfebf
LSHIFT ($b, $a) ; 0 << 65215 = 0 = 0x0000
RSHIFT ($a, $b) ; 65215 >> 0 = 65215 = 0xfebf
OUTPUT (64, 4) ; Output 0xfebf 0000
END-MESSAGE (0, 0, 0, 0, 0, 0, 0)
The output of the code is 0x0150 0000 febf 0000. Executing the code
costs a total of 22 UDVM cycles.
2.2. Arithmetic
This section gives assembly code to test the ADD, SUBTRACT, MULTIPLY,
DIVIDE, and REMAINDER instructions. The code is designed to test
that the following boundary cases have been correctly implemented:
1. The instructions overwrite themselves with the result of the
arithmetic operation, resulting in continuation as if the bytes
were not bytecode.
2. The result does not lie between 0 and 2^16 - 1 inclusive, in
which case it must be taken modulo 2^16.
3. The divisor in the DIVIDE or REMAINDER instructions is 0 (in
which case decompression failure must occur).
at (64)
:a pad (2)
:b pad (2)
:type pad (1)
:type_lsb pad (1)
at (128)
INPUT-BYTES (1, type_lsb, decomp_failure)
SUBTRACT ($type, 1)
JUMP (start)
:decomp_failure
DECOMPRESSION-FAILURE
; Now the value in $type should be 0xffff, 0x0000, or 0x0001
; according to whether the input was 0x00, 0x01, or 0x02.
at (255)
:start
; The multitypes are values
; For all three messages
; $start = 1728 (first 2 bytes of ADD instr)
ADD ($start, 63809) ; 1728 + 63809 = 1 = 0x0001
SUBTRACT ($a, 1) ; 0 - 1 = 65535 = 0xffff
MULTIPLY ($a, 1001) ; 65535 * 1001 = 64535 = 0xfc17
DIVIDE ($a, 101) ; 64535 / 101 = 638 = 0x027e
REMAINDER ($a, 11) ; 638 % 11 = 0 = 0x0000
OUTPUT (64, 4) ; output 0x0000 0000
; The multitypes are references
ADD ($b, $start) ; 0 + 1 = 1 = 0x0001
; If the message is 0x00
SUBTRACT ($b, $type) ; 1 - 65535 = 2 = 0x0002
MULTIPLY ($b, $b) ; 2 * 2 = 4 = 0x0004
DIVIDE ($a, $b) ; 0 / 4 = 0 = 0x0000
REMAINDER ($b, $type) ; 4 % 65535 = 4 = 0x0004
OUTPUT (64, 4) ; output 0x0000 0004
; If the message is 0x01, $type = 0
; so decompression failure occurs at
; REMAINDER ($b, $type)
; If the message is 0x02, $type = 1 so
; $b becomes 0 and decompression failure
; occurs at DIVIDE ($a, $b)
END-MESSAGE (0, 0, 0, 0, 0, 0, 0)
If the compressed message is 0x00, then the output of the code is
0x0000 0000 0000 0004 and the execution cost should be 25 UDVM
cycles. However, if the compressed message is 0x01 or 0x02, then
decompression failure occurs.
2.3. Sorting
This section gives assembly code to test the SORT-ASCENDING and SORT-
DESCENDING instructions. The code is designed to test that the
following boundary cases have been correctly implemented:
1. The sorting instructions sort integers with the same value, in
which case the original ordering of the integers must be
preserved.
at (128)
SORT-DESCENDING (256, 2, 23)
SORT-ASCENDING (256, 2, 23)
OUTPUT (302, 45)
END-MESSAGE (0, 0, 0, 0, 0, 0, 0)
at (256)
word (10, 10, 17, 7, 22, 3, 3, 3, 19, 1, 16, 14, 8, 2, 13, 20, 18,
23, 15, 21, 12, 6, 9)
word (28263, 8297, 30057, 8308, 26996, 11296, 31087, 29991, 8275,
18031, 28263, 24864, 30066, 29284, 28448, 29807, 28206, 11776, 28773,
28704, 28276, 29285, 28265)
The output of the code is 0x466f 7264 2c20 796f 7527 7265 2074 7572
6e69 6e67 2069 6e74 6f20 6120 7065 6e67 7569 6e2e 2053 746f 7020 6974
2e, and the number of cycles required is 371.
2.4. SHA-1
This section gives assembly code to test the SHA-1 instruction. The
code performs four tests on the SHA-1 algorithm itself and, in
addition, checks the following boundary cases specific to the UDVM:
1. The input string for the SHA-1 hash is obtained by byte copying
over an area of the UDVM memory.
2. The SHA-1 hash overwrites its own input string.
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:hash_value pad (20)
at (128)
SHA-1 (test_one, 3, hash_value)
OUTPUT (hash_value, 20)
SHA-1 (test_two, 56, hash_value)
OUTPUT (hash_value, 20)
; Set up a 1-byte buffer
LOAD (byte_copy_left, test_three)
LOAD (byte_copy_right, test_four)
; Perform SHA-1 over 16384 bytes in a 1-byte buffer
SHA-1 (test_three, 16384, hash_value)
OUTPUT (hash_value, 20)
; Set up an 8-byte buffer
LOAD (byte_copy_left, test_four)
LOAD (byte_copy_right, test_end)
; Perform SHA-1 over 640 bytes in an 8-byte buffer
SHA-1 (test_four, 640, test_four)
OUTPUT (test_four, 20)
END-MESSAGE (0, 0, 0, 0, 0, 0, 0)
:test_one
byte (97, 98, 99)
:test_two
byte (97, 98, 99, 100, 98, 99, 100, 101, 99, 100, 101, 102, 100, 101,
102, 103, 101, 102, 103, 104, 102, 103, 104, 105, 103, 104, 105, 106,
104, 105, 106, 107, 105, 106, 107, 108, 106, 107, 108, 109, 107, 108,
109, 110, 108, 109, 110, 111, 109, 110, 111, 112, 110, 111, 112, 113)
:test_three
byte (97)
:test_four
byte (48, 49, 50, 51, 52, 53, 54, 55)
:test_end
The output of the code is as follows:
0xa999 3e36 4706 816a ba3e 2571 7850 c26c 9cd0 d89d
0x8498 3e44 1c3b d26e baae 4aa1 f951 29e5 e546 70f1
0x12ff 347b 4f27 d69e 1f32 8e6f 4b55 73e3 666e 122f
0x4f46 0452 ebb5 6393 4f46 0452 ebb5 6393 4f46 0452
Executing the code costs a total of 17176 UDVM cycles.
2.5. LOAD and MULTILOAD
This section gives assembly code to test the LOAD and MULTILOAD
instructions. The code is designed to test the following boundary
cases:
1. The MULTILOAD instruction overwrites itself or any of its
operands, in which case decompression failure occurs.
2. The memory references of MULTILOAD instruction operands are
evaluated step-by-step rather than all at once before starting to
copy data.
at (64)
:start pad (1)
:start_lsb pad (1)
at (128)
set (location_a, 128)
set (location_b, 132)
LOAD (128, 132) ; address 128 contains 132 = 0x0084
LOAD (130, $location_a) ; address 130 contains 132 = 0x0084
LOAD ($location_a, 134) ; address 132 contains 134 = 0x0086
LOAD ($location_b, $location_b) ; address 134 contains 134 = 0x0086
OUTPUT (128, 8) ; output 0x0084 0084 0086 0086
INPUT-BYTES (1, start_lsb, decompression_failure)
MULTIPLY ($start, 2)
ADD ($start, 60)
MULTILOAD ($start, 3, overlap_start, overlap_end, 128)
:position
set (overlap_start, (position - 7))
MULTILOAD ($start, 4, 42, 128, $location_a, $location_b)
:end
set (overlap_end, (end - 1))
OUTPUT (128, 8)
END-MESSAGE (0, 0, 0, 0, 0, 0, 0)
:decompression_failure
DECOMPRESSION-FAILURE
The INPUT-BYTES, MULTIPLY, and ADD instructions give the following
values for $start = $64 just before the MULTILOADs begin:
Input $start before 1st MULTILOAD
0x00 60
0x01 62
0x02 64
Consequently, after the first MULTILOAD the values of $start are the
following:
Input $start before 2nd MULTILOAD
0x00 128
0x01 overlap_end = 177 = last byte of 2nd MULTILOAD instruction
0x02 overlap_start = 162 = 7 bytes before 2nd MULTILOAD
instruction
Consequently, execution of the 2nd MULTILOAD (and any remaining code)
gives the following:
Input Outcome
0x00 MULTILOAD reads and writes operand by operand. The output is
0x0084 0084 0086 0086 002a 0080 002a 002a, and the cost of
executing the code is 36 UDVM cycles.
0x01 The first write of the MULTILOAD instruction would overwrite
the last byte of the final MULTILOAD operand, so
decompression failure occurs.
0x02 The last write of the MULTILOAD would overwrite the MULTILOAD
opcode, so decompression failure occurs.
2.6. COPY
This section gives assembly code to test the COPY instruction. The
code is designed to test that the following boundary cases have been
correctly implemented:
1. The COPY instruction copies data from both outside the circular
buffer and inside the circular buffer within the same operation.
2. The COPY instruction performs byte-by-byte copying (i.e., some of
the later bytes to be copied are themselves written into the UDVM
memory by the COPY instruction currently being executed).
3. The COPY instruction overwrites itself and continues executing.
4. The COPY instruction overwrites the UDVM registers byte_copy_left
and byte_copy_right.
5. The COPY instruction writes to and reads from the right of the
buffer beginning at byte_copy_right.
6. The COPY instruction implements byte copying rules when the
destination wraps around the buffer.
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
at (128)
; Set up buffer between addresses 64 & 128
LOAD (32, 16384)
LOAD (byte_copy_left, 64)
LOAD (byte_copy_right, 128)
COPY (32, 128, 33) ; Copy byte by byte starting to the left of
; the buffer, into the buffer and wrapping
; the buffer (inc overwriting the
; boundaries)
LOAD (64, 16640) ; Change the start of the buffer to be
; beyond bytecode
COPY (64, 85, 65) ; Copy to the left of the buffer,
; overwriting this instruction
OUTPUT (32, 119) ; Output 32 * 0x40 + 86 * 0x41 + 0x55,
; which is 32 * ’@’ + 86 ’A’ + ’U’
; Set a new small buffer
LOAD (byte_copy_left, 32)
LOAD (byte_copy_right, 48)
MEMSET (32, 4, 65, 1) ; Set first 4 bytes of the buffer to be
; ’ABCD’
COPY (32, 4, 48) ; Copy from byte_copy_right (i.e., not
; in buffer)
OUTPUT (48, 4) ; Output 0x4142 4344, which is ’ABCD’
COPY (48, 4, 46) ; Copy from two before byte_copy_right to
; wrap around the buffer
OUTPUT (32, 2) ; Output 0x4344, which is ’CD’
END-MESSAGE (0, 0, 0, 0, 0, 0, 0)
The output is above, and executing the code costs a total of 365 UDVM
cycles.
2.7. COPY-LITERAL and COPY-OFFSET
This section gives assembly code to test the COPY-LITERAL and COPY-
OFFSET instructions. The code is designed to test similar boundary
cases to the code for the COPY instruction, as well as the following
condition specific to COPY-LITERAL and COPY-OFFSET:
1. The COPY-LITERAL or COPY-OFFSET instruction overwrites the value
of its destination.
2. The COPY-OFFSET instruction reads from an offset that wraps
around the buffer (i.e., the offset is larger than the distance
between byte_copy_left and the destination).
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:destination pad (2)
:offset pad (2)
at (128)
; Set up circular buffer, source, and
; destination
LOAD (32, 16640)
LOAD (byte_copy_left, 64)
LOAD (byte_copy_right, 128)
LOAD (destination, 33)
COPY-LITERAL (32, 128, $destination) ; Copy from the left of the
; buffer overwriting bcl, bcr, and