Ett fel per enhet eller ett fel i en oredovisad enhet ( engelska off-by-one error ) är ett logiskt fel i algoritmen (eller i matematiska beräkningar), inklusive, i synnerhet, en diskret version av brott mot gränsvillkor.
Ett fel uppstår ofta i programmeringen när antalet iterationer av en steg-för-steg- slinga är en mindre eller fler än nödvändigt. Till exempel, när man jämför, indikerar en programmerare "mindre än eller lika" istället för "mindre än", eller gör ett misstag, räknar början av sekvensen inte från noll, utan från en ( arrayindexering i många programmeringsspråk börjar från noll).
Betrakta en array av element där element från m -th till n -th inklusive bearbetas. Hur många medlemmar i arrayen kommer att bearbetas? nm :s svar är ett ett-för-ett-fel och ett exempel på ett "fence-post"-fel. Rätt svar är n-m+1 .
För att reducera fel på grund av oredovisade enheter, representeras indexeringsintervallet ofta som halvöppna intervall. Så intervallet från m till n (inklusive) representeras av intervallet från m (inklusive) till n+1 (inte inklusive det sista värdet). Till exempel kan en slinga som går igenom fem värden skrivas med ett halvöppet intervall från 0 till 5 ( C-språk ):
för ( i = 0 ; i < 5 ; ++ i ) { /* loopkropp */ }Slingkroppen exekveras med start från i lika med 0; i blir då 1, 2, 3 och blir slutligen 4 i nästa steg. När i blir 5 är i<5 inte uppfyllt och slingan slutar. Men om jämförelsevillkoret är <= (mindre än eller lika med), kommer loopen att köras sex gånger: i kommer att anta värdena 0, 1, 2, 3, 4 och 5. På samma sätt, om i är initieras till 1 istället för 0, kommer det bara att finnas 4 iterationer i slingan: jag tar värdena 1, 2, 3 och 4. Båda dessa alternativ leder till ett fel på ett.
Ett liknande fel kan uppstå om en do-while loop används istället för en while loop (eller vice versa). Do-while-loopen garanterar minst en iteration, eftersom villkoret kontrolleras efter att slingans kropp har exekveras.
Array-relaterade fel kan också vara resultatet av skillnader i programmeringsspråk. Att räkna från noll är traditionellt, men vissa språk räknas från 1. Pascal och Fortran kan definiera index [1] . Detta gör att du kan anpassa arraymodellen till ämnesområdet.
Stängselstolpefelet (kallas ibland telegrafstolpen eller lyktstolpsfelet) är ett specialfall av fel per enhet. Följande uppgift illustrerar detta fel:
Man sätter upp ett rakt staket 30 meter långt och sätter upp stolpar var 3:e meter. Hur många stolpar behöver du?
Det "uppenbara" svaret vid första anblicken, 10, är fel.
Staketet har 30 : 3 = 10 sektioner. Men det krävs 11 pelare, en till.
Det omvända felet uppstår när antalet kolumner är känt och antalet sektioner antas vara lika med antalet kolumner. I verkligheten är antalet sektioner en mindre än antalet kolumner.
Mer generellt kan problemet formuleras på följande sätt: om det finns n telegrafstolpar, hur många luckor finns det mellan dem?
Rätt svar kan vara n-1 om raden av stolpar är öppen i båda ändar; n om pelarna bildar en cirkel; n + 1 - om de fria utrymmena i båda ändarna anses vara luckor. Den exakta definitionen av problemet måste noggrant studeras, eftersom en lösning som är korrekt i en situation kan ge ett felaktigt resultat i en annan. Staketstolpsfelet uppstår genom att man räknar stolpar istället för mellanrum mellan dem, eller vice versa, och att man försummar frågan om en eller båda ändarna av en rad behöver beaktas.
Staketstolpsfelet kan även dyka upp vid räkning av andra element än längder. Ett exempel är tidens pyramid , som ska bestå av 120 block, som vart och ett placeras på sin plats med ett intervall på 10 år. Det tar 1190 år att bygga från början av det första blocket till det sista blocket, inte 1200. inte med undantag. På grund av detta, i beräkningen, upprepades skottåret efter 3 år, och inte efter 4.
Staketstolpsfelet kan i sällsynta fall orsakas av en oväntad ordning av indata, vilket till exempel helt kan omintetgöra effektiviteten av att använda ett binärt träd eller exekvera en hashfunktion . Detta fel har att göra med skillnaden mellan algoritmens förväntade och värsta tänkbara beteende.
För stora antal är felet per enhet ofta inte så viktigt i ett särskilt fall. Med små siffror, och i vissa specifika fall där precision är avgörande, kan förekomsten av ett ett-i-ett-fel vara katastrofalt. Ibland kan ett misstag upprepas, och därför förstärkas, genom att personen gör fel beräkning om nästa person gör det misstaget igen (naturligtvis kan detta misstag göras tvärtom också).
Som ett exempel på ett sådant fel kan vi ta funktionen linspace() [2] från Matlabs beräkningsspråk , vars parametrar är: det minsta värdet, det största värdet och antalet värden, och inte: det minsta värdet, det största värdet och antalet steg. En programmerare som missförstår vad den tredje parametern är kommer att anta att linspace(0,10,5) genererar sekvensen [0,2,4,6,8,10] men istället får [0, 2,5, 5, 7,5, 10 ].
Ett vanligt ett-till-ett-fel som leder till ett säkerhetsproblem är felaktig användning av strncat()- funktionen från C - standardbiblioteket . Ett vanligt missförstånd förknippat med strncat() är att en nollbyte [3] inte kan skrivas längre än strängens längd. Funktionen skriver faktiskt en nollbyte utöver den angivna stränglängden om den tredje parametern är lika med eller större än den längden. Följande kod innehåller just ett sådant fel:
void foo ( const char * s ) { charbuf [ 15 ] ; buf [ 0 ] = '\0' ; strncat ( buf , s , sizeof ( buf )); // ERROR - sista parametern måste vara lika med sizeof(buf)-1 }Ett fel är vanligt när man använder standardbiblioteket C, eftersom det inte har ett konsekvent tillvägagångssätt om huruvida 1 ska subtraheras eller inte: funktioner som fgets() och strncpy() kommer aldrig att överskrida sin angivna längd (fgets() subtraherar själv 1 och extraherar (längd-1) bytes), medan andra funktioner som strncat() skriver förbi längden som anges för strängen. Av denna anledning måste programmeraren komma ihåg vilka funktioner som kräver subtrahering av 1.
På vissa system (särskilt de med endian endian-arkitektur) kan detta resultera i att betydande bytes skrivs över på processstacken, vilket kan skapa ett tillstånd där en angripare får data som tillåter honom att anropa en processprocedur [4] .
Ett tillvägagångssätt som kan användas för att lösa sådana problem är att använda en modifiering av dessa funktioner som räknar antalet skrivna byte, med hänsyn till buffertens längd, istället för att skriva eller läsa det maximala antalet byte. Exempel är funktionerna strlcat() och strlcpy() , som ofta anses vara "säkra" eftersom de förhindrar oavsiktliga skrivningar bortom slutet av bufferten (i koden ovan eliminerar anrop av strlcat(buf, s, sizeof(buf)) en säkerhetsfel).