Saturday, January 14, 2017

When Bad Requirements Happen to Good People

Super-famous and very good-looking authors Karl Wiegers and Joy Beatty did a fabulous job of describing this problem in a section titled "When Bad Requirements Happen to Good People" from their amazing book Software Requirements, Third Edition (Microsoft Press, 2013), reprinted here with permission:

When Bad Requirements Happen to Good People
The major consequence of requirements problems is rework—doing again something that you thought was already done—late in development or after release. Rework often consumes 30 to 50 percent of your total development cost, and requirements errors can account for 70 to 85 percent of the rework cost. Some rework does add value and improves the product, but excessive rework is wasteful and frustrating. Imagine how different your life would be if you could cut the rework effort in half! Your team members could build better products faster and perhaps even go home on time. Creating better requirements is an investment, not just a cost.

It can cost far more to correct a defect that’s found late in the project than to fix it shortly after its creation. Suppose it costs $1 (on a relative scale) to find and fix a requirement defect while you’re still working on the requirements. If you discover that error during design instead, you have to pay the $1 to fix the requirement error, plus another $2 or $3 to redo the design that was based on the incorrect requirement. Suppose, though, that no one finds the error until a user calls with a problem. Depending on the type of system, the cost to correct a requirement defect found in operation can be $100 or more on this relative scale. One of my consulting clients determined that they spent an average of $200 of labor effort to find and fix a defect in their information systems using the quality technique of software inspection, a type of peer review. In contrast, they spent an average of $4,200 to fix a single defect reported by the user, an amplification factor of 21. Preventing requirements errors and catching them early clearly has a huge leveraging effect on reducing rework.

Shortcomings in requirements practices pose many risks to project success, where success means delivering a product that satisfies the user’s functional and quality expectations at the agreed-upon cost and schedule.

Saturday, December 31, 2016

Pictorial Effect


The pictorial superiority effect is truly Olympian. Tests performed years ago showed that people could remember more than 2,500 pictures with at least 90 percent accuracy several days later, even though subjects saw each picture for about 10 seconds. (This is recognition memory, not working memory, at work.) Accuracy rates a year later still hovered around 63 percent. In one paper, picture recognition information was reliably retrieved several decades later. Sprinkled throughout these experiments were comparisons with text or oral presentations. The usual result was “picture demolishes them both.” It still does. Text and oral presentations are not just less efficient than pictures for retaining certain types of information; they are far less efficient. If information is presented orally, people remember about 10 percent, tested 72 hours after exposure. That figure goes up to 65 percent if you add a picture.

Why is text less efficient than pictures? Because, it turns out, the brain sees words as lots of tiny pictures. A word is unreadable unless the brain can separately identify simple features in the letters. Instead of words, we see complex little art-museum masterpieces, with hundreds of features embedded in hundreds of letters. Like an art junkie, our brains linger at each feature, rigorously and independently verifying it before moving to the next. So reading creates a bottleneck in comprehension. To our cortex, surprisingly, there is no such thing as words.

That’s not necessarily obvious. After all, the brain is as adaptive as Silly Putty. Given your years of reading books, writing email, and sending text messages, you might think your visual system could be trained to recognize common words without slogging through tedious additional steps of letter-feature recognition. But that is not what happens. No matter how experienced a reader you become, your brain will still stop and ponder the individual features of each letter you read—and do so until you can’t read anymore.

By now, you can probably guess why this might be. Our evolutionary history was never dominated by books or email or text messages. It was dominated by trees and saber-toothed tigers. Vision means so much to us because most of the major threats to our lives in the savannah were apprehended visually. Ditto with most of our food supplies. Ditto with our perceptions of reproductive opportunity.

The tendency is so pervasive that, even when we read, most of us try to visualize what the text is telling us. “Words are only postage stamps delivering the object for you to unwrap,” George Bernard Shaw was fond of saying. A lot of brain science now backs him up.

Tuesday, December 27, 2016

Evolution of an Algorithm

In linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, was the asymptotically fastest known matrix multiplication algorithm until 2010. It can multiply two  matrices in  time. This is an improvement over the naïve  time algorithm and the  time Strassen algorithm. Algorithms with better asymptotic running time than the Strassen algorithm are rarely used in practice, because the large constant factors in their running times make them impractical. It is possible to improve the exponent further; however, the exponent must be at least 2 (because an  matrix has  values, and all of them have to be read at least once to calculate the exact result).
In 2010, Andrew Stothers gave an improvement to the algorithm,  In 2011, Virginia Williams combined a mathematical short-cut from Stothers' paper with her own insights and automated optimization on computers, improving the bound to  In 2014, François Le Gall simplified the methods of Williams and obtained an improved bound of 
The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds. However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.

Source: Wikipedia, Coppersmith–Winograd algorithm

Karatsuba Fast Multiplication Algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most  single-digit multiplications in general (and exactly  when n is a power of 2). It is therefore faster than the classical algorithm, which requires n2 single-digit products. For example, the Karatsuba algorithm requires 310 = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the classical algorithm requires (210)2 = 1,048,576.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm is even faster, for sufficiently large nSource: https://en.wikipedia.org/wiki/Karatsuba_algorithm

Pseudocode:
procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2

  // calculates the size of the numbers
  M = max(size_base10(num1), size_base10(num2))
  N = M/2

  // split the digit sequences about the middle
  high1, low1 = split_at(num1, N)
  high2, low2 = split_at(num2, N)

  // 3 calls made to numbers approximately half the size
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)

  return (z2*10^(2*N))+((z1-z2-z0)*10^(N))+(z0)

Implementation:
public static BigInteger karatsuba(BigInteger x, BigInteger y) {

  // cutoff to brute force
  int M = Math.max(x.bitLength(), y.bitLength());
  if (M <= 2000) return x.multiply(y); // optimize this parameter
  
  // number of bits divided by 2, rounded up
  int N = (M / 2) + (M % 2);
  
  // x = a + 2^N b, y = c + 2^N d
  // x = low1 + 2^N high1, y = low2 + 2^N high2
  BigInteger high1 = x.shiftRight(N);
  BigInteger low1 = x.subtract(high1.shiftLeft(N));
  BigInteger high2 = y.shiftRight(N);
  BigInteger low2 = y.subtract(high2.shiftLeft(N));
  
  // compute sub-expressions
  BigInteger z0 = karatsuba(low1, low2);
  BigInteger z1 = karatsuba(low1.add(high1), low2.add(high2));
  BigInteger z2 = karatsuba(high1, high2);
  
  return z0.add(z1.subtract(z0).subtract(z2).shiftLeft(N)).add(z2.shiftLeft(2*N));
}

Source: http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html

Tuesday, December 13, 2016

Товьёгтой, нийлмэл PDF файл үүсгэх нь

Хичээлийн улирлын эцэст, шалгалтын өмнөхөн, оюутнууд бид баахан PPT, PDF файл сөхөж харах хэрэгтэй болдог. Жишээлэхэд миний одоо авч буй Network & Internet Security хичээл гэхэд л 37 PPT, PDF файл хосолсон слайд, нэмэлт унших материалтай. Энэ бүх файлыг нэгбүрчлэн нээнэ гэдэг их төвөгтэйн дээр, нэгдсэн хайлт хийх боломжоор тун маруу.

PPT файлыг PDF формат руу хөрвүүлээд, гарсан PDF файлуудаа Линуксын pdfunite коммандаар хялбархан нэгтгэж болох ч, товьёг гаргаж өгдөггүй болохоор баахан чамлалттай. Нэг том PDF файл дотроо хүссэн хичээл рүү гээ үсэрч чадаж байвал нь дөхөмтэйсэн.

Ямартай ч, хичээлийнхээ слайдыг бүгдийг нь PDF рүү хөрвүүлчихлээ. pdfdir гэх нээлттэй эхийн програм ашиглаад товьёгтой, нэг том PDF файл үүсгэх гэтэл алдаа заагаад болсонгүй. Алдааг нухаж байх зав байсангүй тул, дараагийн програм болох Sejda Console-г туршиж үзэв. 

sejda-console merge -b one_entry_each_doc -f $(ls netsec/*.pdf) -o NetSec-All-Slides.pdf

Ер нь яг санаснаар нэгтгэж байна. Гарсан үр дүн нь энэ:


Хичээлийн хуваарь болон шалгалтын асуултын тоймыг хамгийн эхэнд тавьж өгөөд, өнөө 37 слайдаа бүгдийг нь нэгтгээд авлаа. Нийт 2,536 хуудастай томоо PDF файл үүсч. Одоо ингээд хичээлийн бүх слайдаас нэг дор хайлт хийх, хүссэн хичээлийн, хүссэн сэдэв рүү хулганы нэг товшилтоор очих боломжтой болов. 4 хоногийн дараах шалгалтаас өмнө лав бүх слайдаа хэд гурав гүйлгээд харчих нь ээ. Болоо ш дэ :)

Өөр бас нэг анзаарсан зүйл нь хэрэв тусдаа байгаа PDF файлуудаа эвтэйхэн паттернтай нэрлэчихвэл нь паттерн тус бүрээр PDF файл үүсгэж болох нь. Жишээ нь энэ хичээлийн слайдууд дараах үндсэн гурван төрлийн слайдуудаас бүрдэж байгаа: 1) Corporate Computer Security ном; 2) CERT-ийн слайд; 3) Cisco-н слайд.

Corporate Computer Security номын слайдын нэр '-bk' тэмдэгт агуулж байгаа тул доорх коммандаар зөвхөн энэ номын слайдуудыг нэгтгэж болох нь:
sejda-console merge -b one_entry_each_doc -f $(ls netsec/*-bk*.pdf) -o CorpCompSecBook.pdf

CERT-н слайдын нэр '-cert' тэмдэгт агуулж байгаа тул доорх коммандаар зөвхөн CERT-н слайдыг нэгтгэж болох нь:
sejda-console merge -b one_entry_each_doc -f $(ls netsec/*-cert*.pdf) -o CERT-Slides.pdf

Cisco-н слайдууд 'Cisco' тэмдэгт агуулж байгаа тул доорх коммандаар зөвхөн Cisco-н слайдуудыг нэгтгэж болох нь:
sejda-console merge -b one_entry_each_doc -f $(ls netsec/*Cisco*.pdf) -o Cisco-Slides.pdf

Эцэст нь, ингэхэд энэ нөхөр ямар файлуудыг нэгтгэчихэв гэж та гайхаж байж магад. Хариу нь энэ:
[bsanchin@bsanchin-linux netsec]$ ls -1 | while read f; do du -h $f; done | awk '{print $2, $1}' | column -t
W00-1-Syllabus.pdf                                                   384K
W00-2-Final_Exam_Study_Topics.pdf                                    288K
W01-bk1-The_Threat_Environment.pdf                                   7.2M
W01-bk2-Planning_and_Policy.pdf                                      9.5M
W01-cert-Governance.pdf                                              1.1M
W01-cert-Risk_Management.pdf                                         1.2M
W02-Ch01-Cisco-Introduction_to_Switched_Networks.pdf                 464K
W02-Ch02-Cisco-Introduction_to_Switched_Networks.pdf                 1.3M
W02-Ch03-Cisco-WLANs.pdf                                             896K
W02-Ch04-Routing_Concepts.pdf                                        1.7M
W03-cert-Demystifying_IPv6.pdf                                       3.2M
W03-IP_Fundamentals-CCNA1v3.1_Mod09.pdf                              1016K
W03-The_OSI_Model_and_Security.pdf                                   896K
W04-bk-Security_Networks.pdf                                         9.3M
W04-cert-LAN_security_using_switch_featuresv2.pdf                    1.8M
W04-Suppl1-Securing_the_LAN.pdf                                      5.2M
W04-Target_Breach.pdf                                                5.2M
W05-cert-Network_Security-Wireless.pdf                               1.1M
W05-Merging_LANs,_WLANS,_and_controller-based_Wireless_Networks.pdf  2.8M
W06-bk-Access_Control.pdf                                            12M
W06-cert-Network_Access_Security.pdf                                 1.7M
W06-Password_Recovery_Procedure_for_the_2600_Router.pdf              20K
W07-bk-Firewalls.pdf                                                 12M
W07-cert-Network_Security_Enterprise_Tools.pdf                       2.1M
W08-bk-Host_Hardening.pdf                                            9.1M
W08-cert-Network_Security_Host_Hardening.pdf                         688K
W09-bk-Data_Protection.pdf                                           8.0M
W09-cert-Mobile_Device_Security.pdf                                  4.4M
W09-cert-Threats_to_Mobile_Device.pdf                                2.4M
W09-Implementing_VPN_-_Cisco-CCNA.pdf                                4.5M
W10-cert-Insider_Threat.pdf                                          3.2M
W11-bk-Application_Security.pdf                                      6.0M
W11-Common_Developer_Crypto_Mistakes.pdf                             372K
W12-bk-Data_Protection.pdf                                           7.4M
W13-bk-Incident_and_Disaster_Response.pdf                            8.6M
W13-cert-IncidentHandlingResponse.pdf                                1.9M
W14-cert-Cloud_Computing_Security.pdf                                2.2M
W15-MS-cert1-Mobile_Threats.pdf                                      2.4M
W15-MS-cert2-Mobile_Device_Security.pdf                              4.4M
[bsanchin@bsanchin-linux netsec]$ 

Яг энэ постыг уншаад сууж байгаа эрхэм та оюутан бол шалгалтанд тань өндөр амжилтыг хүсье!