Off-by-one 오류

Off-by-one error

오프 바이 원 에러 또는 오프 바이 원 버그(약어 OBOE, OBO, OB1 및 OBOB)는 경계 조건과 동등한 이산 에러입니다.컴퓨터 프로그래밍에서 반복 루프가 너무 많거나 너무 적을 때 자주 발생합니다.이 문제는 프로그래머가 비교에서 "보다 작거나 같음"을 사용했어야 하는 "보다 작음"을 사용하는 등의 실수를 하거나 시퀀스가 1이 아닌 0에서 시작된다는 점을 고려하지 않았을 때 발생할 수 있습니다(많은 언어의 배열 인덱스와 같음).이는 수학적 맥락에서도 발생할 수 있습니다.

경우들

어레이를 통한 루프

항목 배열로 간주하여 m부터 n까지(포함) 항목을 처리한다.몇 개 있어요?직관적인 답은 n - m일 수 있지만, 1개씩 빗나가 펜스 포스트 오류를 나타냅니다. 정답은 (n – m) + 1입니다.

이 때문에 컴퓨팅의 범위는 반오픈 인터벌로 표시되는 경우가 많습니다.펜스 포스트 오류를 피하기 위해 m ~n(포함)의 범위로 나타냅니다.포함)~n+1(포함)의 범위로 나타냅니다.예를 들어, 5회 반복하는 루프(0 ~4 포함)는, 0 ~5 의 하프 오픈 인터벌로서 쓸 수 있습니다.

위해서 (색인 = 0; 색인 < > 5; 색인++)  {     /* 루프의 본체 */ }

루프 본체는 우선 다음과 같이 실행됩니다.인덱스는 0이 됩니다.지수는 연속적인 반복으로 1, 2, 3, 마지막으로 4가 됩니다.이 시점에서 인덱스는 5가 되므로 인덱스 <5는 false이며 루프는 종료됩니다.단, 사용된 비교가 <=(이하)일 경우 루프는 6회 실행됩니다.인덱스는 값 0, 1, 2, 3, 4, 및 5를 취합니다.마찬가지로 인덱스를 0이 아닌 1로 초기화할 경우 4회만 반복됩니다. 즉, 인덱스는 값 1, 2, 3, 4를 취합니다.이 두 가지 방법 모두 하나씩 오류를 일으킬 수 있습니다.

while 루프 대신 do-while 루프가 사용되는 경우(또는 그 반대)에도 이러한 오류가 발생할 수 있습니다.do-while 루프는 적어도1회 실행이 보증됩니다.

프로그래밍 언어의 차이로 인해 어레이와 관련된 혼란도 발생할 수 있습니다.0부터 번호를 매기는 것이 가장 일반적이지만 일부 언어에서는 배열 번호를 1로 시작합니다. Pascal에는 사용자 정의 인덱스가 있는 배열이 있습니다.이를 통해 문제 도메인을 따라 배열 인덱스를 모델링할 수 있습니다.

펜스 포스트 오류

n개의 섹션이 있는 직선 펜스는 n+1개의 기둥을 가지고 있다.

펜스 포스트 오류(전봇대, 램프 포스트 또는 피켓 펜스 오류라고도 함)는 특정 유형의 오프 바이 원 오류입니다.이 오류에 대한 초기 설명은 비트루비우스의 [1]작품에서 나타납니다.다음 문제는 에러를 나타내고 있습니다.

30피트 길이의 직선 울타리를 만들고 기둥을 3피트 간격으로 세우면 기둥은 몇 개 필요합니까?

10개의 게시물에 대한 일반적인 답변은 틀렸습니다.이 응답은 펜스의 길이를 각 기둥에서 떨어져 있는 간격으로 나누면 나타나며, 지수가 기둥 수로 잘못 분류됩니다.실제로 울타리는 10개의 부분과 11개의 기둥으로 이루어져 있다.

이 시나리오에서는 n개의 섹션이 있는 펜스는 n개의 +1개의 기둥을 가집니다.반대로 펜스에 n개의 포스트가 포함되어 있는 경우 n - 1개의 섹션이 포함됩니다.이 관계는 역오류를 처리할 때 고려해야 합니다.게시물의 수가 이미 알려져 있고 섹션의 수가 같다고 가정할 때 역오류가 발생합니다.펜스의 설계에 따라 이 가정이 정확하거나 정확하지 않을 수 있습니다.

다음 문제는 역방향 오류를 나타냅니다.

게시물이 n개일 경우 게시물 사이에 몇 개의 섹션이 있습니까?

울타리 설계에 대한 해석은 이 문제에 대한 답을 바꾼다.펜스의 정확한 섹션 수는 펜스가 각각의 끝단에서 기둥에 의해 경계된 독립 선분(예: 두 통로 간격 사이의 펜스)인 경우 n - 1이고, 펜스가 하나의 완전한 독립 루프(예: 박싱 링과 같은 극복으로 접근할 수 있는 인클로저)를 형성하는 경우 n - 1이며, 포스트가 발생하지 않는 경우 n + 1이다.선분 모양의 울타리(예: 두 건물 사이의 울타리 및 벽면).한 상황에 대한 설정이 다른 상황에 대한 잘못된 답을 제공할 수 있으므로 정확한 문제 정의를 신중하게 고려해야 합니다.펜스 포스트 오류는 그 사이에 공백이 있는 것이 아니라 수를 세는 것이 원인입니다.또는 그 반대도 마찬가지입니다.또, 행의 한쪽 끝을 세는 것과 양쪽 끝을 세는 것 중 어느 쪽 끝을 세는 것을 잊는 것이 원인입니다.

펜스 포스트 오류는 길이 이외의 단위로도 발생할 수 있습니다.예를 들어 블록 사이에 10년 간격으로 배치된 120개의 블록으로 구성된 시간 피라미드는 첫 번째 블록 설치부터 마지막 블록까지 1,190년이 소요될 예정입니다.최초의 펜스 포스트 오류 중 하나는 원래 율리우스력이 윤년을 잘못 계산했던 시간과 관련이 있는데, 이는 4년마다가 아닌 3년마다 윤년을 산출하는 것이 아니라 포괄적으로 계산했기 때문입니다.

"펜스포스트 오류"는 드물게 입력값의 [2]예기치 않은 규칙성에 의해 유발되는 오류를 나타낼 수 있으며, 이론적으로 효율적인 바이너리 트리 또는 해시 함수 구현을 완전히 방해할 수 있습니다.이 오류에는 알고리즘의 예상 동작과 최악의 경우 동작의 차이가 포함됩니다.

더 많은 경우, 한 명이 쉬는 것은 큰 문제가 되지 않습니다.그러나 수가 적고 정확도가 가장 중요한 경우 오프 바이 원 오류를 커밋하는 것은 치명적일 수 있습니다.이러한 문제가 반복될 수 있으며, 따라서 다음 사람이 같은 종류의 실수를 다시 하면 잘못된 계산을 통해 악화될 수 있습니다(물론 오류도 반전될 수 있습니다).

이 오류의 예는 MATLAB에서 발생할 수 있습니다.linspace() 매개 변수가 다음과 같은 선형 보간 함수(lower value, upper value, number of values)가 아니라(lower value, upper value, number of increments)세 번째 매개변수를 증분 수로 오해하는 프로그래머는 다음과 같이 생각할 수 있습니다.linspace(0,10,5)는 시퀀스를 달성하지만 대신 취득합니다.

보안상의 영향

보안 관련 버그를 일으키는 일반적인 오프 바이 원 에러는 C 표준 라이브러리의 오용으로 인해 발생합니다. strncat일과.와의 일반적인 오해strncat보증된 늘 터미네이션이 최대 길이를 넘지 않는 것입니다.실제로는 지정된 최대 길이를 1바이트 초과하여 끝의 늘 문자를 씁니다.다음 코드에는 이러한 버그가 포함되어 있습니다.

무효 후우 (차 *s)  {     차 부프[15];     메모리 세트(부프, 0, 크기(부프));     스트론캣(부프, s, 크기(부프)); // 최종 파라미터는 size of(buf)-1이어야 합니다. }

C 라이브러리를 사용할 때 1바이트를 빼야 하는지 여부에 대해 일관성이 없기 때문에 오프바이원 에러는 흔히 발생합니다.– 다음과 같은 함수입니다.fgets()그리고.strncpy지정된 길이를 초과하여 쓸 수 없습니다(fgets()1을 빼고 (length - 1)바이트만 가져옵니다.그 외의 경우는, 다음과 같습니다.strncat지정된 길이를 초과하여 쓸 수 있습니다.그래서 프로그래머는 어떤 함수에 대해 1을 빼야 하는지 기억해야 한다.

일부 시스템(특히 작은 엔디안 아키텍처)에서 이것은 프레임 포인터의 최하위 바이트의 덮어쓰기를 초래할 수 있습니다.이로 인해 공격자가 호출 루틴의 로컬 변수를 가로채는 공격 가능한 상태가 발생할 수 있습니다.

이러한 문제를 회피하는 데 도움이 되는 한 가지 방법은 쓰는 최대 글자 수가 아니라 버퍼의 총 길이를 기준으로 쓰는 양을 계산하는 이러한 함수의 변형을 사용하는 것입니다.이러한 기능에는 다음이 포함됩니다.strlcat그리고.strlcpy버퍼의 끝을 지나 잘못 쓰는 것을 피하기 쉽기 때문에, 「안전」하다고 생각되는 경우가 많습니다(위의 코드 예에서는, 콜을 발신하고 있습니다).strlcat(buf, s, sizeof(buf))대신 버그를 제거합니다.)

「 」를 참조해 주세요.

레퍼런스

인용문

  1. ^ 를 클릭합니다Moniot, Robert K., Who first described the "fence-post error?", Fordham University, archived from the original on 2016-03-05, retrieved 2016-07-07.
  2. ^ Raymond, Eric. "The Jargon File". Retrieved 17 May 2021.

원천

추가 정보

  • Parker, Matt (2021). Humble Pi: When Math Goes Wrong in the Real World. Riverhead Books. ISBN 978-0593084694.