Figure 11 lists the different instructions and the bytecode values used to encode the instructions. The cost of each instruction in UDVM cycles is also given:
Instruction: Bytecode value: Cost in UDVM cycles: DECOMPRESSION-FAILURE 0 1 AND 1 1 OR 2 1 NOT 3 1 LSHIFT 4 1 RSHIFT 5 1 ADD 6 1 SUBTRACT 7 1 MULTIPLY 8 1 DIVIDE 9 1 REMAINDER 10 1 SORT-ASCENDING 11 1 + k * (ceiling(log2(k)) + n) SORT-DESCENDING 12 1 + k * (ceiling(log2(k)) + n) SHA-1 13 1 + length LOAD 14 1 MULTILOAD 15 1 + n PUSH 16 1 POP 17 1 COPY 18 1 + length COPY-LITERAL 19 1 + length COPY-OFFSET 20 1 + length MEMSET 21 1 + length JUMP 22 1 COMPARE 23 1 CALL 24 1 RETURN 25 1 SWITCH 26 1 + n CRC 27 1 + length INPUT-BYTES 28 1 + length INPUT-BITS 29 1 INPUT-HUFFMAN 30 1 + n STATE-ACCESS 31 1 + state_length STATE-CREATE 32 1 + state_length STATE-FREE 33 1 OUTPUT 34 1 + output_length END-MESSAGE 35 1 + state_length Figure 11: UDVM instructions and corresponding bytecode values Each UDVM instruction costs a minimum of 1 UDVM cycle. Certain instructions may cost additional cycles depending on the values of the instruction operands. Named variables in the cost expressions refer to the values of the instruction operands with these names. Note that for the SORT instructions, the formula ceiling(log2(k)) calculates the smallest value i such that k <= 2^i.
The UDVM instruction set offers a mix of low-level and high-level instructions. The high-level instructions can all be emulated using combinations of low-level instructions, but given a choice it is generally preferable to use a single instruction rather than a large number of general-purpose instructions. The resulting bytecode will be more compact (leading to a higher overall compression ratio) and decompression will typically be faster because the implementation of the high-level instructions can be more easily optimized. All instructions are encoded as a single byte to indicate the instruction type, followed by 0 or more bytes containing the operands required by the instruction. The instruction specifies which of the four operand types of Section 8.5 is used in each case. For example the ADD instruction is followed by two operands: ADD ($operand_1, %operand_2) When converted into bytecode the number of bytes required by the ADD instruction depends on the value of each operand, and whether the multitype operand contains the operand value itself or a memory address where the actual value of the operand can be found. Each instruction is explained in more detail below. Whenever the description of an instruction uses the expression "and then", the intended semantics is that the effect explained before "and then" is completed before work on the effect explained after the "and then" is commenced.
After the operation is complete, the value of the first operand is overwritten with the result. (Note that since this operand is a reference, it is the 2-byte word at the memory address specified by the operand that is overwritten.) The precise definitions of LSHIFT and RSHIFT are given below. Note that m and n are the 2-byte values encoded by the operands, and that floor(x) calculates the largest integer not greater than x: LSHIFT (m, n) := m * 2^n (modulo 2^16) RSHIFT (m, n) := floor(m / 2^n)
The block of data itself is divided into n lists each containing k 2-byte words. The SORT-ASCENDING instruction applies a certain permutation to the lists, such that the first list is sorted into ascending order (treating each 2-byte word as an unsigned integer). The same permutation is applied to all n lists, so lists other than the first will not necessarily be sorted into order. In the case that two words have the same value, the original ordering of the list is preserved. For example, the first list might contain a set of integers to be sorted whilst the second list might be used to keep track of where the integers appear in the sorted list: Before sorting After sorting List 1 List 2 List 1 List 2 8 1 1 2 1 2 1 3 1 3 3 4 3 4 8 1 The SORT-DESCENDING instruction behaves as above, except that the first list is sorted into descending order. RFC-3174] over the specified area of UDVM memory. SHA-1 (%position, %length, %destination) The position and length operands specify the starting memory address and the length of the byte string over which the SHA-1 hash is calculated. Byte copying rules are enforced as per Section 8.4. The destination operand gives the starting address to which the resulting 20-byte hash will be copied. Byte copying rules are enforced as above.
Section 8.3). PUSH (%value) POP (%address) The PUSH instruction pushes the value specified by its operand on the stack. The POP instruction pops a value from the stack and then copies the value to the specified memory address. (Note that the expression "and then" implies that the copying of the value is inconsequential for the stack operation itself, which happens beforehand.) See Section 8.3 for possible error conditions.
Section 8.4. Section 8.4 with m set to the destination address of the last byte to be copied, if any (i.e., if the value of the length operand is zero, the value of the destination operand is not changed).
The COPY-OFFSET instruction then behaves as a COPY-LITERAL instruction, taking the value of the position operand to be the last memory address reached in the above step. Section 8.4. (Note that the byte string may overwrite the MEMSET instruction or its operands; as explained in Section 8.5, the MEMSET instruction must be executed as if the original operands were still in place in the UDVM memory.) Section 9.4) can also alter program flow.
Section 8.3. When the UDVM reaches a CALL instruction, it finds the memory address of the instruction immediately following the CALL instruction and pushes this 2-byte value on the stack, ready for later retrieval. It then continues instruction execution at the memory address specified by the address operand. When the UDVM reaches a RETURN instruction it pops a value from the stack and then continues instruction execution at the memory address just popped. See Section 8.3 for error conditions.
RFC-1662]. The position and length operands define the string of bytes over which the CRC is evaluated. Byte copying rules are enforced as per Section 8.4. The CRC value is computed exactly as defined for the 16-bit FCS calculation in [RFC-1662]. The value operand contains the expected integer value of the 2-byte CRC. If the calculated CRC matches the expected value then the UDVM continues instruction execution at the following instruction. Otherwise the UDVM jumps to the memory address specified by the address operand.
The length operand indicates the requested number of bytes of compressed data, and the destination operand specifies the starting memory address to which they should be copied. Byte copying is performed as per the rules of Section 8.4. If the instruction requests data that lies beyond the end of the SigComp message, no data is returned. Instead the UDVM moves program execution to the address specified by the address operand. If the INPUT-BYTES is encountered after an INPUT-BITS or an INPUT- HUFFMAN instruction has been used, and the dispatcher currently holds a fraction of a byte, then the fraction MUST be discarded before any data is passed to the UDVM. The first byte to be passed is the byte immediately following the discarded data. Section 8.2. If the instruction requests data that lies beyond the end of the SigComp message, no data is returned. Instead the UDVM moves program execution to the address specified by the address operand.
INPUT-HUFFMAN (%destination, @address, #n, %bits_1, %lower_bound_1, %upper_bound_1, %uncompressed_1, ... , %bits_n, %lower_bound_n, %upper_bound_n, %uncompressed_n) Note that if n = 0 then the INPUT-HUFFMAN instruction is ignored and program execution resumes at the following instruction. Decompression failure occurs if (bits_1 + ... + bits_n) > 16. In all other cases, the behavior of the INPUT-HUFFMAN instruction is defined below: 1. Set j := 1 and set H := 0. 2. Request bits_j compressed bits. Interpret the returned bits as an integer k from 0 to 2^bits_j - 1, as explained in Section 8.2. 3. Set H := H * 2^bits_j + k. 4. If data is requested that lies beyond the end of the SigComp message, terminate the INPUT-HUFFMAN instruction and move program execution to the memory address specified by the address operand. 5. If (H < lower_bound_j) or (H > upper_bound_j) then set j := j + 1. Then go back to Step 2, unless j > n in which case decompression failure occurs. 6. Copy (H + uncompressed_j - lower_bound_j) modulo 2^16 to the memory address specified by the destination operand. Section 7.2. Decompression failure occurs if partial_identifier_length does not lie between 6 and 20 inclusive. Decompression failure also occurs if no state item matching the partial state identifier can be found, if
more than one state item matches the partial identifier, or if partial_identifier_length is less than the minimum_access_length of the matched state item. Otherwise, a state item is returned from the state handler. If any of the operands state_address, state_instruction or state_length is set to 0 then its value is taken from the returned item of state instead. Note that when calculating the number of UDVM cycles the STATE-ACCESS instruction costs (1 + state_length) cycles. The value of state_length MUST be taken from the returned item of state in the case that the state_length operand is set to 0. The state_begin and state_length operands define the starting byte and number of bytes to copy from the state_value contained in the returned item of state. Decompression failure occurs if bytes are copied from beyond the end of the state_value. Note that decompression failure will always occur if the state_length operand is set to 0 but the state_begin operand is non-zero. The state_address operand contains a UDVM memory address. The requested portion of the state_value is byte copied to this memory address using the rules of Section 8.4. Program execution then resumes at the memory address specified by state_instruction, unless this address is 0 in which case program execution resumes at the next instruction following the STATE-ACCESS instruction. Note that the latter case only occurs if both the state_instruction operand and the state_instruction value from the requested state are set to 0. Section 9.4.9.
Decompression failure MUST occur if more than four state creation requests are made before the END-MESSAGE instruction is encountered. Decompression failure also occurs if the minimum_access_length does not lie between 6 and 20 inclusive, or if the state_retention_priority is 65535. Section 9.4.9. Decompression failure MUST occur if more than four state free requests are made before the END-MESSAGE instruction is encountered. Decompression failure also occurs if partial_identifier_length does not lie between 6 and 20 inclusive. Section 8.4. Decompression failure occurs if the cumulative number of bytes provided to the dispatcher exceeds 65536 bytes.
Since there is technically a difference between outputting a 0-byte decompressed message, and not outputting a decompressed message at all, the OUTPUT instruction needs to distinguish between the two cases. Thus, if the UDVM terminates before encountering an OUTPUT instruction it is considered not to have outputted a decompressed message. If it encounters one or more OUTPUT instructions, each of which provides 0 bytes of data to the dispatcher, then it is considered to have outputted a 0-byte decompressed message.
Note that there is a maximum limit of four state creation requests per instance of the UDVM. Therefore, decompression failure occurs if the END-MESSAGE instruction makes a state creation request and four instances of the STATE-CREATE instruction have already been encountered. When creating a state item it is necessary to give the state_length, state address, state_instruction and minimum_access_length; these are supplied as operands in the STATE-CREATE instruction (or the END- MESSAGE instruction). A complete item of state also requires a state_value and a state_identifier, which are derived as follows: The UDVM byte copies a string of state_length bytes from the UDVM memory beginning at state_address (obeying the rules of Section 8.4). This is the state_value. The UDVM then calculates a 20-byte SHA-1 hash [RFC-3174] over the byte string formed by concatenating the state_length, state_address, state_instruction, minimum_access_length and state_value (in the order given). This is the state_identifier. The state_retention_priority is not part of the state item itself, but instead determines the order in which state will be deleted when the compartment exceeds its allocated state memory. The state_retention_priority is supplied as an operand in the STATE- CREATE or END-MESSAGE instruction and is passed to the state handler as part of each state creation request. The state free requests are made by the STATE-FREE instruction. Each STATE-FREE instruction supplies the values partial_identifier_start and partial_identifier_length; upon reaching the END-MESSAGE instruction these values are used to byte copy a partial state identifier from the UDVM memory. If no state item matching the partial state identifier can be found or if more than one state item in the compartment matches the partial state identifier, then the state free request is ignored (this does not cause decompression failure to occur). Otherwise, the state handler frees the matched state item as specified in Section 6.2. As well as forwarding the state creation and state free requests, the END-MESSAGE instruction may also pass feedback data to the state handler. Feedback data is used to inform the receiving endpoint about the capabilities of the sending endpoint, which can help to improve the overall compression ratio and to reduce the working memory requirements of the endpoints.
Two types of feedback data are available: requested feedback and returned feedback. The format of the requested feedback data is given in Figure 12. As outlined in Section 3.2, the requested feedback data can be used to influence the contents of the returned feedback data in the reverse direction. The returned feedback data is itself subdivided into a returned feedback item and a list of returned SigComp parameters. The returned feedback item is of sufficient importance to warrant its own field in the SigComp header as described in Section 7.1. The returned SigComp parameters are illustrated in Figure 13. Note that the formats of Figure 12 and Figure 13 are only for local presentation of the feedback data on the interface between the UDVM and state handler. The formats do not mandate any bits on the wire; the compressor can transmit the data in any form provided that it is loaded into the UDVM memory at the correct addresses. Moreover, the responsibility for ensuring that feedback data arrives successfully over an unreliable transport lies with the sender. The receiving endpoint always uses the last received value for each field in the feedback data, even if the values are out of date due to packet loss or misordering. If the requested_feedback_location operand is set to 0, then no feedback request is made; otherwise, it points to the starting memory address of the requested feedback data as shown in Figure 12. 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | reserved | Q | S | I | requested_feedback_location +---+---+---+---+---+---+---+---+ | | : requested feedback item : if Q = 1 | | +---+---+---+---+---+---+---+---+ Figure 12: Format of requested feedback data The reserved bits may be used in future versions of SigComp, and are set to 0 in Version 0x01. Non-zero values should be ignored by the receiving endpoint. The Q-bit indicates whether a requested feedback item is present or not. The compressor can set the requested feedback item to an arbitrary value, which will then be transmitted unmodified in the reverse direction as a returned feedback item. See Chapter 5 for further details of how the requested feedback item is returned.
The format of the requested feedback item is identical to the format of the returned feedback item illustrated in Figure 4. The compressor sets the S-bit to 1 if it does not wish (or no longer wishes) to save state information at the receiving endpoint and also does not wish to access state information that it has previously saved. Consequently, if the S-bit is set to 1 then the receiving endpoint can reclaim the state memory allocated to the remote compressor and set the state_memory_size for the compartment to 0. The compressor may change its mind and switch the S-bit back to 0 in a later message. However, the receiving endpoint is under no obligation to use the original state_memory_size for the compartment; it may choose to allocate less memory to the compartment or possibly none at all. Similarly the compressor sets the I-bit to 1 if it does not wish (or no longer wishes) to access any of the locally available state items offered by the receiving endpoint. This can help to conserve bandwidth because the list of locally available state items no longer needs to be returned in the reverse direction. It may also conserve memory at the receiving endpoint, as the state handler can delete any locally available state items that it determines are no longer required by any remote endpoint. Note that the compressor can set the I-bit back to 0 in a later message, but it cannot access any locally available state items that were previously offered by the receiving endpoint unless they are subsequently re-announced. If the returned_parameters_location operand is set to 0, then no SigComp parameters are returned; otherwise, it points to the starting memory address of the returned parameters as shown in Figure 13.
0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | cpb | dms | sms | returned_parameters_location +---+---+---+---+---+---+---+---+ | SigComp_version | +---+---+---+---+---+---+---+---+ | length_of_partial_state_ID_1 | +---+---+---+---+---+---+---+---+ | | : partial_state_identifier_1 : | | +---+---+---+---+---+---+---+---+ : : +---+---+---+---+---+---+---+---+ | length_of_partial_state_ID_n | +---+---+---+---+---+---+---+---+ | | : partial_state_identifier_n : | | +---+---+---+---+---+---+---+---+ Figure 13: Format of returned SigComp parameters The first byte encodes the SigComp parameters cycles_per_bit, decompression_memory_size and state_memory_size as per Section 3.3.1. The byte can be set to 0 if the three parameters are not included in the feedback data. (This may be useful to save bits in the compressed message if the remote endpoint is already satisfied all necessary information has reached the endpoint receiving the message.) The second byte encodes the SigComp_version as per Section 3.3.2. Similar to the first byte, the second byte can be set to 0 if the parameter is not included in the feedback data. The remaining bytes encode a list of partial state identifiers for the locally available state items offered by the sending endpoint. Each state item is encoded as a 1-byte length field, followed by a partial state identifier containing as many bytes as indicated in the length field. The sender can choose to send as few as 6 bytes if it believes that this is sufficient for the receiver to determine which state item is being offered. The list of state identifiers is terminated by a byte in the position where the next length field would be expected that is set to a value below 6 or above 20. Note that upgraded SigComp versions may append additional items of data after the final length field.
- Attacking SigComp as the DoS target by filling it with state: Excessive state can only be installed by a malicious sender (or a set of malicious senders) with the consent of the application. The system consisting of SigComp and application is thus approximately as vulnerable as the application itself, unless it allows the installation of SigComp state from a message where it would not have installed application state itself. If this is desirable to increase the compression ratio, the effect can be mitigated by making use of feedback at the application level that indicates whether the state requested was actually installed - this allows a system under attack to gracefully degrade by no longer installing compressor state that is not matched by application state. Obviously, if a stream-based transport is used, the streams themselves constitute state that has to be handled in the same way that the application itself would handle a stream-based transport; if an application is not equipped for stream-based transport, it should not allow SigComp connections on a stream-based transport. For the alternative SigComp usage described as "continuous mode" in Section 4.2.1, an attacker could create any number of active UDVMs unless there is some DoS protection at a lower level (e.g., by using TLS in appropriate configurations). - Attacking the UDVM by faking state or making unauthorized changes to state: This is covered in Section 10.2.2. - Attacking the UDVM by sending it looping code: The application sets an upper limit to the number of "UDVM cycles" that can be used per compressed message and per input bit in the compressed message. The damage inflicted by sending packets with looping code is therefore limited, although this may still be substantial if a large number of UDVM cycles are offered by the UDVM. However, this would be true for any decompressor that can receive packets over an unsecured transport.
Following the policies outlined in [RFC-2434], the IANA policy for assigning a new value for the SigComp_version shall require a Standards Action. Values are thus assigned only for Standards Track RFCs approved by the IESG. [RFC-1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, July 1994. [RFC-2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC-3174] Eastlake, 3rd, D. and P. Jones, "US Secure Hash Algorithm 1 (SHA1)", RFC 3174, September 2001. [RFC-1951] Deutsch, P., "DEFLATE Compressed Data Format Specification version 1.3", RFC 1951, May 1996. [RFC-2026] Bradner, S., "The Internet Standards Process - Revision 3", BCP 9, RFC 2026, October 1996. [RFC-2279] Yergeau, F., "UTF-8, a transformation format of ISO 10646", RFC 2279, January 1998.
[RFC-2326] Schulzrinne, H., Rao, A. and R. Lanphier, "Real Time Streaming Protocol (RTSP)", RFC 2326, April 1998. [RFC-2434] Alvestrand, H. and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. [RFC-2960] Stewart, R., Xie, Q., Morneault, K., Sharp, C., Schwartzbauer, H., Taylor, T., Rytina, I., Kalla, M., Zhang, L. and V. Paxson, "Stream Control Transmission Protocol", RFC 2960, October 2000. [RFC-3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M. and E. Schooler, "SIP: Session Initiation Protocol", RFC 3261, June 2002. [RFC-3321] Hannu, H., Christoffersson, J., Forsgren, S., Leung, K.-C., Liu, Z. and R. Price, "Signaling Compression (SigComp) - Extended Operations", RFC 3321, January 2003.
Jan Christoffersson Box 920 Ericsson AB SE-971 28 Lulea, Sweden Phone: +46 920 20 28 40 EMail: firstname.lastname@example.org Hans Hannu Box 920 Ericsson AB SE-971 28 Lulea, Sweden Phone: +46 920 20 21 84 EMail: email@example.com Zhigang Liu Nokia Research Center 6000 Connection Drive Irving, TX 75039 Phone: +1 972 894-5935 EMail: firstname.lastname@example.org Jonathan Rosenberg dynamicsoft 72 Eagle Rock Avenue First Floor East Hanover, NJ 07936 EMail: email@example.com
Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.