CST8118 Computer Binary Overflow PDF

CST8118 Computer Essentials Computer Binary Overflow  Week 5: Computer Binary Overflow Binary Addition in Mathematics Computer Limitations Computer Limitations – Add Unsigned Numbers Computer Limitations – Add Signed Numbers Integer Overflow Defined Integer Un...

CST8118 Computer Essentials Computer Binary Overflow  Week 5: Computer Binary Overflow Binary Addition in Mathematics Computer Limitations Computer Limitations – Add Unsigned Numbers Computer Limitations – Add Signed Numbers Integer Overflow Defined Integer Underflow Why are we (programmers) concerned with overflow? Ariane 5 Rocket (Example) Patriot Missile Failure (Example) How to Prevent or Detect Overflow 2  Binary Addition in Mathematics In mathematics there is no limit on the number of bits available to store the result of adding two binary numbers. For example, image taken from showing addition of 2310 + 5310 The result is larger than either of the two operands, in math-class this is okay. We are only limited by paper, pencil, and our imagination. 3  Computer Limitations Computers have limited amounts of memory to store numeric data. A term “word” is often used to represent the number of contiguous bits used natively by a computer processor. Common word sizes for current computers are 32-bit and 64-bit. As a programmer we are normally more concerned with the number of bits for a data type, if the data type is signed or un-signed, and when performing arithmetic if an overflow, underflow, or carry has occurred. E.g. Java int data type is signed, and uses 32 bits of memory E.g. Java char data type is unsigned, and uses 16 bits of memory 4  Computer Limitations – Add Unsigned Numbers The computer is limited in the number of bits it can use to represent the result of an arithmetic operation. For unsigned numbers we can overflow and carryout. For example, (image taken from ), the result cannot be stored into 8 bits of memory so the carry is lost (discarded), and the resulting sum is not correct. 49 + 228 should be 277 But the computers result is 21 (Max value for unsigned byte is 255) This incorrect result is referred to as overflow. Author also goes on to state that for unsigned numbers, overflow and carry out occur together, but not always for signed numbers. 5  Computer Limitations – Add Signed Numbers The computer is limited in the number of bits it can use to represent the result of an arithmetic operation. For signed numbers we can overflow, and not necessarily with a carryout. For example, with two’s compliment, (image taken from ), the result cannot be stored so the carry is lost (discarded), and the resulting sum is not correct. 127 + 1 should be 128 But the computers result is -128 (Max value for signed byte is 127) This incorrect result is referred to as overflow. Author also goes on to state that for unsigned numbers, overflow and carry out occur together, but not always for signed numbers. 6  Integer Overflow Defined Integer Overflow When an arithmetic result cannot be stored within the range of binary digits available to the computer (number of bits). This can be above the max value, as well as below the min value E.g. a Java 8-bit byte can only represent -128 to 127 (inclusive) suggests that three simple rules can be used to detect overflow (quoted text): 1. If the sum of two positive numbers yields a negative result, the sum has overflowed. 2. If the sum of two negative numbers yields a positive result, the sum has overflowed. 3. Otherwise, the sum has not overflowed 7  Integer Underflow Some authors use the term underflow for the case where two negative numbers are added, and the result is below the minimum range for the computer. This is more correctly called negative overflow. Underflow is: The result of the calculation is too small to be represented by the data type. E.g. in mathematics 1 / 3 will be 0.3333 (3 repeating) E.g. in Java 1 / 3 underflows and becomes 0 i.e. 0.3333 is too small to be represented by a Java integer type which cannot represent fractional numbers. 8  Why are we (programmers) concerned with overflow? Overflow errors in computer programs have security concerns, as well as safety concerns that can result in financial loss, and loss of life. Some notable examples: Ariane 5 Rocket (financial loss) Patriot Missile Failure (loss of human life) 9  Ariane 5 Rocket According to the first flight of the Arianespace Ariane 5 rocket failed, due to an integer overflow which lead to the rocket exploding shortly after launch. The rocket was carrying satellites into space, and allegedly cost a financial loss of more than $370 million US dollars. Video footage of the rocket exploding can be found on YouTube. https://www.youtube.com/watch?v=gp_D8r-2hwk (See time 0:33) Allegedly the software from the Ariane 4 rocket was re-used, with the Ariane 5. However the Ariane 5 had different flight dynamics, which caused an overflow in the Ariane 4 software. The onboard computer performed an automatic course- correction causing the rocket to fail, then self-destruct (explode). 10  Patriot Missile Failure According to on Feb 25, 1991 an overflow error within the software controlling the patriot missile caused the death of 28 soldiers and injuring around 100 other people. An overflow inside the missiles guidance system caused a musculation resulting in the missile striking an American Army Barracks instead of an incoming Iraqi Scud missile. 11  How to Prevent or Detect Overflow There are a variety of strategies to prevent and / or detect overflow of integer data types in a programming language. Check the values of your variables before performing a calculation to predict if they will overflow (can be difficult to work out the logic reliably). Check for overflow after performing a calculation (easier, but reactive). Use a larger data type which will not overflow, then check result. Use the API of the programming language where possible. If two positive numbers are added, is the result negative? If two negative numbers are added, is the result positive? 12  Conclusion Binary Addition in Mathematics Computer Limitations Computer Limitations – Add Unsigned Numbers Computer Limitations – Add Signed Numbers Integer Overflow Defined Integer Underflow Why are we (programmers) concerned with overflow? Ariane 5 Rocket (Example) Patriot Missile Failure (Example) How to Prevent or Detect Overflow 13  Sources Cited Dr. Bennet. Binary Addition Examples. sandbox.mc.edu. http://sandbox.mc.edu/~bennet/cs110/pm/add.html (Last Accessed Feb 19, 2023) Word (computer architecture). wikipedia.org. https://en.wikipedia.org/wiki/Word_(computer_architecture) (Last Accessed Feb 19, 2023) Dr. Bennet. Eight-Bit Binary Addition Examples. sandbox.mc.edu. http://sandbox.mc.edu/~bennet/cs110/pm/add8.html (Last Accessed Feb 19, 2023) Dr. Bennet. Two's Complment Binary Addition Examples. sandbox.mc.edu. http://sandbox.mc.edu/~bennet/cs110/tc/add.html(Last Accessed Feb 19, 2023) Integer overflow. wikipedia.org. https://en.wikipedia.org/wiki/Integer_overflow (Last Accessed Feb 19, 2023) 14  Sources Cited Dr. Bennet. Two's Complement Overflow Rules. sandbox.mc.edu. http://sandbox.mc.edu/~bennet/cs110/tc/orules.html (Last Accessed Feb 19, 2023) Srinivas. What is integer overflow and underflow? resources.infosecinstitute.com. https://resources.infosecinstitute.com/topic/what-is-is-integer-overflow-and-underflow/ (Last Accessed Feb 19, 2023) KushalP, Ivar, BalusC, Durandal, Jim, fragorl, l. Popescu, reprogrammer, P. Tillemans, Dusan, user4267316, lobzik, J. Woo. How does Java handle integer underflows and overflows and how would you check for it? stackoverflow.com. https://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and- overflows-and-how-would-you-check-fo (Last Accessed Feb 19, 2023) - scroll down to the answer by Jim on Jul 19, 2012. Arithmetic underflow. wikipedia.org. https://en.wikipedia.org/wiki/Arithmetic_underflow (Last Accessed Feb 19, 2023) 15  Sources Cited Ariane flight V88. wikipedia.org. https://en.wikipedia.org/wiki/Ariane_flight_V88 (Last Accessed Feb 19, 2023) JeiceTheWarrior. Longer video of 'Ariane 5' Rocket first launch failure/explosion. [video online] https://www.youtube.com/watch?v=gp_D8r-2hwk (Last Accessed Feb 19, 2023) - See time 0:33 Some disasters attributable to bad numerical computing. iro.umontreal.ca. https://www.iro.umontreal.ca/~mignotte/IFT2425/Disasters.html (Last Accessed Feb 19, 2023) 16  Sources Cited J. McManus, R. Schiela. NUM00-J. Detect or prevent integer overflow. wiki.sei.cmu.edu https://wiki.sei.cmu.edu/confluence/display/java/NUM00-J. +Detect+or+prevent+integer+overflow (Last Accessed Feb 19, 2023) M. Krimgen. Overflow and Underflow in Java:4.2. Throw an Exception. baeldung.com. https://www.baeldung.com/java-overflow-underflow#2-throw-an-exception (Last Accessed Feb 19, 2023) Check for Integer Overflow. geeksforgeeks.org. https://www.geeksforgeeks.org/check-for- integer-overflow/ (Last Accessed Feb 19, 2023) 17  Recommended Resources Binary to Decimal converter. rapidtables.com. https://www.rapidtables.com/convert/number/binary-to-decimal.html (Last Accessed Feb 19, 2023) Dr. Bennet. Binary and Boolean Examples. sandbox.mc.edu. http://sandbox.mc.edu/~bennet/cs110/index.html (Last Accessed Feb 19, 2023) - this is the index page for several other related web pages. J. McManus, R. Schiela. SEI CERT Oracle Coding Standard for Java. wiki.sei.cmu.edu. https://wiki.sei.cmu.edu/confluence/display/java/ SEI+CERT+Oracle+Coding+Standard+for+Java (Last Accessed Feb 19, 2023) M.S. Schmalz. Organization of Computer Systems:§ 3: Computer Arithmetic. cise.ufl.edu. https://www.cise.ufl.edu/~mssz/CompOrg/CDA-arith.html (Last Accessed Feb 19, 2023) 18  Recommended Resources Ajbsharing. Binary: converting decimal to binary (part 1 of 2). [video online] https://youtu.be/qWxiXU02ZQM (Accessed Feb 19, 2023) Ajbsharing. Binary: converting binary to decimal (part 2 of 2). [video online] https://youtu.be/UUqtjb8WEUs (Accessed Feb 19, 2023) K. Maycock. Binary to Decimal Conversion and back again!. [video online] https://youtu.be/ZR0pC6_iW5Q (Accessed Feb 19, 2023) The Organic Chemistry Tutor. Adding and Subtracting Binary numbers. [video online]. https://www.youtube.com/watch?v=C5EkxfNEMjE (Accessed Feb 19, 2023) I. D. Allen. The CARRY flag and OVERFLOW flag in binary arithmetic. teaching.idallen.com. https://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt (Accessed Feb 19, 2023) 19  Recommended Resources J. Villete. Java makes use of the “two’s complement” for representing signed numbers. medium.com. https://medium.com/@jeanvillete/java-makes-use-of-the-twos-complement-for- representing-signed-numbers-31e421725c04 (Accessed Feb 15, 2023) The Organic Chemistry Tutor. Binary Addition and Subtraction With Negative Numbers, 2's Complements & Signed Magnitude. [video online]. https://www.youtube.com/watch? v=sJXTo3EZoxM (Accessed Feb 15, 2023) D. Harris, S. Harris. Digital Design and Computer Architecture, 2nd Ed. Chapter 1 Section 1.4 Number Systems. [available online] https://learning.oreilly.com/library/view/digital-design-and/9780123944245/xhtml/ CHP001.html#ST0045 (Last Accessed Feb 13, 2023) Difference between 1's complement Representation and 2's complement Representation. javatpoint.com. https://www.javatpoint.com/1s-complement-representation-vs-2s-complement- representation (Last Accessed Feb 19, 2023) 20