C / C ++에서 서명 된 오버플로 감지

C / C ++에서 서명 된 오버플로 감지

---

언뜻보기 에이 질문은 정수 오버플로를 감지하는 방법 의 중복처럼 보일 수 있습니다 . 그러나 실제로는 상당히 다릅니다.

서명되지 않은 정수 오버플로를 감지하는 것은 매우 사소한 일이지만 C / C ++에서 서명 된 오버플로를 감지하는 것은 실제로 대부분의 사람들이 생각하는 것보다 더 어렵다는 것을 발견했습니다.

가장 분명하지만 순진한 방법은 다음과 같습니다.

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

문제는 C 표준에 따르면 부호있는 정수 오버플로가 정의되지 않은 동작이라는 것입니다. 즉, 표준에 따르면 서명 된 오버플로가 발생하는 즉시 널 포인터를 역 참조한 것처럼 프로그램이 유효하지 않습니다. 따라서 정의되지 않은 동작을 유발할 수 없으며 위의 사후 조건 검사 예제에서와 같이 사실 후에 오버플로를 감지하려고 시도합니다.

위의 검사가 많은 컴파일러에서 작동 할 가능성이 있지만 믿을 수는 없습니다. 실제로 C 표준에서는 부호있는 정수 오버플로가 정의되지 않는다고 말하고 있기 때문에 일부 컴파일러 (예 : GCC)는 최적화 플래그가 설정 될 때 위의 검사 를 최적화합니다. 컴파일러는 부호있는 오버플로가 불가능하다고 가정하기 때문입니다. 이것은 오버플로를 확인하려는 시도를 완전히 중단합니다.

따라서 오버플로를 확인하는 또 다른 가능한 방법은 다음과 같습니다.

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

이러한 추가를 수행해도 오버플로가 발생하지 않는다는 것을 미리 확인할 때까지 실제로 두 정수를 함께 추가하지 않기 때문에 이것은 더 유망 해 보입니다. 따라서 정의되지 않은 동작이 발생하지 않습니다.

그러나이 솔루션은 더하기 연산이 작동하는지 테스트하기 위해 빼기 연산을 수행해야하므로 초기 솔루션보다 훨씬 덜 효율적입니다. 그리고이 (작은) 성능 저하에 대해 신경 쓰지 않더라도이 솔루션이 적절하다고 확신하지는 않습니다. 이 표현식 lhs <= INT_MIN - rhs은 컴파일러가 최적화 할 수있는 표현식과 똑같이 보입니다. 서명 된 오버플로가 불가능하다고 생각합니다.

여기에 더 나은 해결책이 있습니까? 1) 정의되지 않은 동작을 일으키지 않고 2) 컴파일러에게 오버플로 검사를 최적화 할 기회를 제공하지 않는 것이 보장되는 것입니까? 두 피연산자를 unsigned로 캐스팅하고 자신의 2의 보수 산술을 롤링하여 검사를 수행하는 방법이있을 수 있다고 생각했지만 어떻게해야할지 모르겠습니다.

---

빼기에 대한 접근 방식은 정확하고 잘 정의되어 있습니다. 컴파일러는이를 최적화 할 수 없습니다.

더 큰 정수 유형을 사용할 수있는 경우 또 다른 올바른 접근 방식은 더 큰 유형에서 산술을 수행 한 다음 다시 변환 할 때 결과가 더 작은 유형에 맞는지 확인하는 것입니다.

int sum(int a, int b)
{
    long long c;
    assert(LLONG_MAX>INT_MAX);
    c = (long long)a + b;
    if (c < INT_MIN || c > INT_MAX) abort();
    return c;
}

좋은 컴파일러는 전체 추가 및 if명령문을 int크기 추가 및 단일 조건부 오버 플로우 로 변환해야하며 실제로 더 큰 추가를 수행하지 않아야합니다.

편집 : Stephen이 지적했듯이 정상적인 asm을 생성하기 위해 (그다지 좋지 않은) 컴파일러 gcc를 얻는 데 문제가 있습니다. 생성되는 코드는 그렇게 느리지는 않지만 확실히 차선책입니다. gcc가 옳은 일을하도록하는이 코드의 변형을 아는 사람이 있다면보고 싶습니다.

---

아니요, 두 번째 코드가 올바르지 않지만 가까이 있습니다.

int half = INT_MAX/2;
int half1 = half + 1;

추가 결과는 INT_MAX입니다. ( INT_MAX항상 홀수). 그래서 이것은 유효한 입력입니다. 그러나 당신의 일상에서 당신은 가질 INT_MAX - half == half1것이고 당신은 중단 할 것입니다. 거짓 양성.

이 오류는 두 검사를 모두 입력하는 <대신 입력하여 복구 할 수 있습니다 <=.

그러나 코드도 최적이 아닙니다. 다음을 수행합니다.

int add(int lhs, int rhs)
{
 if (lhs >= 0) {
  if (INT_MAX - lhs < rhs) {
   /* would overflow */
   abort();
  }
 }
 else {
  if (rhs < INT_MIN - lhs) {
   /* would overflow */
   abort();
  }
 }
 return lhs + rhs;
}

이것이 유효한지 확인하려면 lhs부등식의 양쪽에 상징적으로 추가 해야합니다. 그러면 결과가 범위를 벗어난 산술적 조건이 정확하게 제공됩니다.

---

IMHO, 오버플로 센시티브 C ++ 코드를 처리하는 가장 쉬운 방법은 SafeInt<T>. 이것은 여기에서 원하는 안전 보장을 제공하는 코드 플렉스에서 호스팅되는 크로스 플랫폼 C ++ 템플릿입니다.

• http://safeint.codeplex.com/

일반적인 수치 연산과 동일한 사용 패턴을 많이 제공하고 예외를 통해 흐름의 위와 아래를 표현하므로 사용하는 것이 매우 직관적입니다.

---

For the gcc case, from gcc 5.0 Release notes we can see it now provides a __builtin_add_overflow for checking overflow in addition:

오버플로 검사를 사용하는 산술을위한 새로운 내장 함수 세트가 추가되었습니다 : __builtin_add_overflow, __builtin_sub_overflow 및 __builtin_mul_overflow 및 clang과의 호환성을 위해 다른 변형도 추가되었습니다. 이러한 내장 기능에는 두 개의 정수 인수 (동일한 유형일 필요 없음)가 있으며, 인수는 무한 정밀도 부호있는 유형으로 확장되고, +,-또는 *가 수행되며 결과는 가리키는 정수 변수에 저장됩니다. 마지막 주장으로. 저장된 값이 무한 정밀도 결과와 같으면 내장 함수는 false를 리턴하고 그렇지 않으면 true를 리턴합니다. 결과를 보유 할 정수 변수의 유형은 처음 두 인수의 유형과 다를 수 있습니다.

예를 들면 :

__builtin_add_overflow( rhs, lhs, &result )

gcc 문서 에서 Overflow Checking 을 사용 하여 산술을 수행하는 내장 함수를 볼 수 있습니다 .

[...] 이러한 내장 함수에는 모든 인수 값에 대해 완전히 정의 된 동작이 있습니다.

clang은 또한 확인 된 산술 내장 집합을 제공합니다 .

Clang은 C에서 빠르고 쉽게 표현할 수있는 방식으로 보안에 중요한 애플리케이션에 대해 검사 된 산술을 구현하는 내장 세트를 제공합니다.

이 경우 내장은 다음과 같습니다.

__builtin_sadd_overflow( rhs, lhs, &result )

---

인라인 어셈블러를 사용하는 경우 오버플로 플래그를 확인할 수 있습니다 . 또 다른 가능성은 safeint 데이터 유형을 사용할 수 있다는 것입니다 . Integer Security 에 대한이 문서를 읽는 것이 좋습니다 .

---

가장 빠른 방법은 내장 GCC를 사용하는 것입니다.

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort();
    return sum;
}

x86에서 GCC는 이것을 다음과 같이 컴파일합니다.

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

프로세서의 내장 오버플로 감지를 사용합니다.

GCC 내장 기능을 사용하는 것이 좋지 않은 경우 다음으로 빠른 방법은 부호 비트에서 비트 연산을 사용하는 것입니다. 서명 된 오버플로는 다음과 같은 경우에 발생합니다.

• 두 피연산자의 부호가 같고
• 결과는 피연산자와 다른 부호를 갖습니다.

의 부호 비트는 ~(lhs ^ rhs)피연산자에 동일한 부호가 있으면 on이고 부호 비트 lhs ^ sum는 결과에 피연산자와 다른 부호가 있으면 온입니다. 따라서 정의되지 않은 동작을 피하기 위해 서명되지 않은 형식으로 추가를 수행 한 다음의 부호 비트를 사용할 수 있습니다 ~(lhs ^ rhs) & (lhs ^ sum).

int add(int lhs, int rhs) {
    unsigned sum = (unsigned) lhs + (unsigned) rhs;
    if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
        abort();
    return (int) sum;
}

이것은 다음과 같이 컴파일됩니다.

    lea (%rsi,%rdi), %eax
    xor %edi, %esi
    not %esi
    xor %eax, %edi
    test %edi, %esi
    js call_abort
    ret
call_abort:
    call abort

32 비트 머신 (gcc 사용)에서 64 비트 유형으로 캐스팅하는 것보다 훨씬 빠릅니다.

    push %ebx
    mov 12(%esp), %ecx
    mov 8(%esp), %eax
    mov %ecx, %ebx
    sar $31, %ebx
    clt
    add %ecx, %eax
    adc %ebx, %edx
    mov %eax, %ecx
    add $-2147483648, %ecx
    mov %edx, %ebx
    adc $0, %ebx
    cmp $0, %ebx
    ja call_abort
    pop %ebx
    ret
call_abort:
    call abort

---

어때 :

int sum(int n1, int n2)
{
  int result;
  if (n1 >= 0)
  {
    result = (n1 - INT_MAX)+n2; /* Can't overflow */
    if (result > 0) return INT_MAX; else return (result + INT_MAX);
  }
  else
  {
    result = (n1 - INT_MIN)+n2; /* Can't overflow */
    if (0 > result) return INT_MIN; else return (result + INT_MIN);
  }
}

I think that should work for any legitimate INT_MIN and INT_MAX (symmetrical or not); the function as shown clips, but it should be obvious how to get other behaviors).

---

You may have better luck converting to 64-bit integers and testing similar conditions like that. For example:

#include <stdint.h>

...

int64_t sum = (int64_t)lhs + (int64_t)rhs;
if (sum < INT_MIN || sum > INT_MAX) {
    // Overflow occurred!
}
else {
    return sum;
}

You may want to take a closer look at how sign extension will work here, but I think it is correct.

---

The obvious solution is to convert to unsigned, to get the well-defined unsigned overflow behavior:

int add(int lhs, int rhs) 
{ 
   int sum = (unsigned)lhs + (unsigned)rhs; 
   if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { 
      /* an overflow has occurred */ 
      abort(); 
   } 
   return sum;  
} 

This replaces the undefined signed overflow behavior with the implementation-defined conversion of out-of-range values between signed and unsigned, so you need to check your compiler's documentation to know exactly what will happen, but it should at least be well defined, and should do the right thing on any twos-complement machine that doesn't raise signals on conversions, which is pretty much every machine and C compiler built in the last 20 years.

---

In case of adding two long values, portable code can split the long value into low and high int parts (or into short parts in case long has the same size as int):

static_assert(sizeof(long) == 2*sizeof(int), "");
long a, b;
int ai[2] = {int(a), int(a >> (8*sizeof(int)))};
int bi[2] = {int(b), int(b >> (8*sizeof(int))});
... use the 'long' type to add the elements of 'ai' and 'bi'

Using inline assembly is the fastest way if targeting a particular CPU:

long a, b;
bool overflow;
#ifdef __amd64__
    asm (
        "addq %2, %0; seto %1"
        : "+r" (a), "=ro" (overflow)
        : "ro" (b)
    );
#else
    #error "unsupported CPU"
#endif
if(overflow) ...
// The result is stored in variable 'a'

---

I think that this works:

int add(int lhs, int rhs) {
   volatile int sum = lhs + rhs;
   if (lhs != (sum - rhs) ) {
       /* overflow */
       //errno = ERANGE;
       abort();
   }
   return sum;
}

Using volatile keeps the compiler from optimizing away the test because it thinks that sum may have changed between the addition and the subtraction.

Using gcc 4.4.3 for x86_64 the assembly for this code does do the addition, the subtraction, and the test, though it stores everything on the stack and of unneeded stack operations. I even tried register volatile int sum = but the assembly was the same.

For a version with only int sum = (no volatile or register) the function did not do the test and did the addition using only one lea instruction (lea is Load Effective Address and is often used to do addition without touching the flags register).

Your version is larger code and has a lot more jumps, but I don't know which would be better.

---

By me, the simpliest check would be checking the signs of the operands and of the results.

Let's examine sum: the overflow could occur in both directions, + or -, only when both operands have the same sign. And, obviosly, the overflow will be when the sign of the result won't be the same as the sign of the operands.

So, a check like this will be enough:

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

Edit: as Nils suggested, this is the correct if condition:

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

And since when the instruction

add eax, ebx 

leads to undefined behavior? There is no such thing in the Intel x86 instruction set refference..

참고URL : https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c