tag:blogger.com,1999:blog-70296054383348757412024-03-12T17:10:21.234-07:00Eitan Adler's thoughtsEitan Adler's thoughts<br>
<small>trying to understand how computers work</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.comBlogger53125tag:blogger.com,1999:blog-7029605438334875741.post-5222846308882835612018-10-11T14:06:00.000-07:002020-01-07T11:35:41.392-08:00Impossible BugsMany bugs are confusing. Others are are annoying. Some are just impossible. This is a list of those bugs:<br />
<ol>
<li><a href="https://www.reddit.com/r/sysadmin/comments/9mk2o7/mri_disabled_every_ios_device_in_facility/">MRI disabled every iOS device in facility</a></li>
<li><a href="http://web.mit.edu/jemorris/humor/500-miles">We can't send mail more than 500 miles</a></li>
<li><a href="https://bugs.launchpad.net/ubuntu/+source/cupsys/+bug/255161">OpenOffice.org can't print on Tuesday</a> (see <a href="https://bugs.launchpad.net/ubuntu/+source/cupsys/+bug/255161/comments/28">comment 28</a>)</li>
<li><a href="https://www.reddit.com/r/talesfromtechsupport/comments/3v52pw/i_cant_log_in_when_i_stand_up/">I can't log in when I stand up.</a> (and another <a href="https://books.google.co.uk/books?id=kse_7qbWbjsC&lpg=PA56&ots=DhvZuTyM9x&pg=PA56">similar story</a>)</li>
<li><a href="http://www.catb.org/jargon/html/magic-story.html">A story about "magic"</a></li>
<li><a href="https://nedbatchelder.com/blog/200811/print_this_file_your_printer_will_jam.html">Print this file, your printer will jam</a></li>
<li>gcj crashes in <a href="https://bugs.launchpad.net/ubuntu/+source/pdftk/+bug/779908/comments/11">April and December, but only if you speak German in Austria</a></li>
<li><a href="https://www.reddit.com/r/talesfromtechsupport/comments/3v3gnj/processor_5_has_failed/">Processor 5 doesn't work if you're standing too close</a></li>
<li>A car that is <a href="http://www.cgl.uwaterloo.ca/smann/IceCream/humor.html"e>allergic to vanilla ice cream</a></li>
<li>Some employees <a href="https://www.reddit.com/r/sysadmin/comments/aiqzhr/user_submits_what_i_thought_was_the_dumbest/">change the monitor's resolution without touching it.</a></li>
<li>The computer is <a href="https://www.reddit.com/r/talesfromtechsupport/comments/6bxlmf/the_oddest_ticket_ive_ever_worked/">filled with bees</a></li>
<li>My chair <a href="https://support.displaylink.com/knowledgebase/articles/738618-display-intermittently-blanking-flickering-or-los">turns off my monitor</a> (<a href="https://twitter.com/royvanrijn/status/1214162400666103808?s=21">via tweet</a>)</li>
</ol>
I'm sure there are more. Let me know!<br/>
<small>Updated 2019-01-22: added additional bug</small><br/>
<small>Updated 2020-01-07: added chair turning off monitor</small><br/>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-65002694683760783122018-06-01T15:28:00.000-07:002018-06-11T11:28:05.398-07:00Good Defaults for Technical DecisionsIn my experience as a software engineer I've found a few "rules of thumb" for technical decisions. None of these are hard requirements or things that can never be false. However these are good guidelines if you don't have a reason to make a different decision.
Unlike most engineering decisions which first present the constraints and then try and find a solution within them, this attempts to document decisions one should make if you didn't have any constraints in the first place.
<br />
Its possible you'll disagree with me on some of these and I'd like to understand why. That said, I'm not interested in <em>specific</em> projects where these are a bad idea but for an understanding about why these shouldn't be the default.<br />
<ol>
<li>Be explicit about your requirements. Don't automatically detect features, dependencies, or environment related issues. It is easier to change this later to make things more "magical" than go back and figure out what you need.</li>
<li>Namespaces are good: even if you think you'll only ever need one. Its easier to modify in the future, versioning, etc.</li>
<li>Errors ought to error. Warning ought to error or not exist. It is generally unhelpful to have noise in your output that you do nothing with. If a warning isn't meaningful, disable it.</li>
<li>Keep scope local and private. Prefer hiding functions and information from the outside unless you have to decided to make this an API. </li>
<li>Naming your first version as a "v1" and label it as such. During rewrites, migrations, or related issues prefer versions rather than names such as "next" or "new". There will likely be many "nexts" and only one v2.</li>
<li>Structured is better than unstructured. Similar to the point about explicitness: it is easier to go from structured to unstructured than vice versa.</li>
<li>Fixed is better than editable. Don't let people change things unless there is a reason to. This also applies to code (immutable is better than mutable).</li>
<li>Don't rely on people not making mistakes. Even if you have perfect people, they might be tired, have something in their eye, misremember a fact, or otherwise be operating at a sub-optimal state.</li>
<li>Name same things the same and different things differently. Use, and accept, the same formats for the same thing at all layers of the stack. As a counter example ruby outputs missing gems as <samp>name-version</samp> but gem(1) expects <samp>name:version</samp>.</li>
</ol>
<div>
This is a work in progress document and I'll try and update it over time</div>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com1tag:blogger.com,1999:blog-7029605438334875741.post-77215614376721283072018-02-17T01:19:00.001-08:002018-02-17T01:41:52.871-08:00Some rules for designing libc style APIs<ol>
<li>Identifiers should not have vowels; they are expensive and difficult to type.</li>
<li>An identifier must not be longer than 8 characters. The only exception are functions intended for standardization like <tt>sched_ss_init_budget</tt>.</li>
<li>Functions must not be reentrant. Relying on internal state means you can avoid allocating memory.</li>
<li>Functions should take at least two parameters. The second parameter should be a "flags" parameter which causes the function to do entirely different things.</li>
<li>Flags should be passed as macros with unspecified values. These macros must not have reasonable values.</li>
<li>Error handling must be done in one of two ways. The choice must not be consistent with other functions in the library:<ol>
<li>The real return value should be stored in an "out" parameter. The return value must only determine if an error has occurred or not.</li>
<li>If an error occurs, the return value must be undefined. The return value can't be safely used without checking for errors using a separate function (e.g., <tt>fgets</tt>).</li></ol></li>
<li>The error code should be in errno, requiring the setting of `errno = 0` beforehand and checking after an error occurs. However, the return value should be a value legally allowed to be in errno, so that initial attempts to use the function appear to work.</li>
<li>If the function returns a string, it must do so by modifying a memory location given as a parameter. Whether or not the string is terminated with a null must be determined solely based on the length of the output, a user supplied parameter, and choice of compiler.</li>
</ol>
<small>Thanks to jp, okdana for the inspiration and review; thanks to gonzo, arbrock for review.</small>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-36418657234128770222016-11-27T13:29:00.003-08:002022-04-05T09:22:47.069-07:00Papers We ReadSome months ago I started a reading group at my workplace focussed on distributed systems. The goal of the group was to be an informal meeting to discuss a mixture of high impact, historical, and modern papers.<br />
<br />
This is the list of papers we read:<br />
<ol>
<li><a href="http://amturing.acm.org/p558-lamport.pdf">Lamport Time Clocks</a></li>
<li><a href="https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf">Spanner: Google’s Globally-Distributed Database</a></li>
<li><a href="https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf">The Chubby Lock Service for Loosely-Coupled</a></li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.7628">A note on distributed computing</a></li>
<li><a href="http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf">The Byzantine Generals Problem</a></li>
<li><a href="https://www.usenix.org/legacy/events/hotos09/tech/full_papers/baumann/baumann.pdf">Your computer is already a distributed system. Why isn't your OS?</a></li>
<li><a href="http://web.mit.edu/2.75/resources/random/How%20Complex%20Systems%20Fail.pdf">How Complex Systems Fail</a></li>
<li><a href="http://ieeexplore.ieee.org/document/5401156/">Fast and Message-Efficient Global Snapshot Algorithms for Large-Scale Distributed Systems</a></li>
<li><a href="https://www.umiacs.umd.edu/~jimmylin/publications/Leibert_etal_SoCC2011.pdf">Automatic Management of Partitioned, Replicated Search Services</a></li>
<li><a href="https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-yuan.pdf">Simple Testing Can Prevent Most Critical Failures</a></li>
<li><a href="https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf">Dynamo: Amazon’s Highly Available Key-value Store</a></li>
<li><a href="https://www.usenix.org/event/atc10/tech/full_papers/Hunt.pdf">Wait-free coordination for Internet-scale system</a></li>
<li>Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services</li>
<li>SEDA: An Architecture for Well-Conditioned, Scalable Internet Services</li>
<li>Kafka: a Distributed Messaging System for Log Processing</li>
<li>DistributedLog: A high performance replicated log service </li>
<li>The Log: What every software engineer should know about real-time data's unifying abstraction</li>
<li>Social Hash: an Assignment Framework for Optimizing Distributed Systems Operations on Social Networks</li>
<li>Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications </li>
<li>MapReduce: Simplified Data Processing on Large Clusters</li>
<li>Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center</li>
<li>MillWheel: Fault-Tolerant Stream Processing at Internet Scale</li>
<li>Snowflake - Unique ID Generation. “No two snowflakes are alike.”</li>
<li>The Hadoop Distributed File System</li>
<li>Gorilla: A Fast, Scalable, In-Memory Time Series Database</li>
<li>Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial</li>
<li>Meltdown</li>
<li>Spectre Attacks: Exploiting Speculative Execution</li>
<li>Communicating Sequential Processes</li>
<li>The Tail at Scale</li>
<li><a href="http://courses.cse.tamu.edu/caverlee/csce438/readings/consistent-hashing.pdf">Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web</a></li>
<li><a href="https://ai.google/research/pubs/pub36356">Dapper, A Large Scale Distributed Systems Tracing Infrastructure</a></li>
<li>The many faces of consistency</li>
<li>SDPaxos: Building efficient semi-decentralized geo-replicated state machines</li>
<li>Dataflow Model</li>
<li><a href="https://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf">How to read a paper</a></li>
<li><a href="https://storage.googleapis.com/pub-tools-public-publication-data/pdf/43837.pdf">Jupiter Rising: A Decade of Clos Topologies andCentralized Control in Google’s Datacenter Network</a></li>
<li>Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook</li>
<li> Harvest, Yield, and Scalable Tolerant Systems</li>
<li>Lineage stash: fault tolerance off the critical path.</li>
<li><a href="http://www.vldb.org/pvldb/vol11/p1835-samwel.pdf">F1 Query: Declarative Querying at Scale</a></li>
<li>The Architectural Implications of Facebook’s DNN-based Personalized Recommendation</li>
<li> EFLOPS: Algorithm and System Co-design for a High Performance Distributed Training Platform</li>
</ol>
<div>
Other papers mentioned but not discussed:</div>
<div>
<ul>
<li><a href="http://www.triodia.com/staff/michi/blog/Another_note.pdf">Another Note on Distributed Computing</a></li>
<li><a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.4847">Implementing remote procedure calls</a></li>
<li><a href="https://isotropic.org/papers/chicken.pdf">Chicken</a></li>
</ul>
<small>
Updated 2018-05-31: added additional papers<br>
Updated 2018-06-20: added additional papers. Linkified a few more<br>
Updated 2018-10-06: added additional papers. Linkified a few more<br>
Updated 2019-07-10: added additional papers. Linkified a few more<br>
Updated 2022-04-05: added additional papers. Linkified a few more<br>
</small></div>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-5462604563356262732015-06-15T21:13:00.000-07:002015-06-15T22:06:09.371-07:00Blogging My Way Through CLRS Section 4.1After another long break of not writing up any CLRS answers here is section 4.1.
<dl>
<dt><b>Question 4.1-1: </b><p>What does $\textit{Find-Maximum-Subarray}$ return when all elements of $A$ are negative?</p></dt>
<dd><p>The procedure would return the single element of maximum value. This is expected since the maximum subarray must contain at least one element. This can be computed by note that $\textit{Find-Max-Crossing-Subarray}$ will always return the array of solely the midpoint and that $\textit{Find-Maximum-Subarray}$ always finds the maxium of $\{leftsum, rightsum, and crosssum\}$ </p></dd>
<dt><b>Question 4.1-2: </b><p>Write pseudocode for the brute-force method of solving the max-subarray problem. Your solution should run in $\theta(n^2)$ time.</p></dt>
<dd><p>
<code style="background-color: #f2f2f2; display: block;">
max_i = <em>nil</em><br>
max_j = <em>nil</em><br>
max_sum = -∞<br>
<br>
for i in 0..len(A):<br>
cur_sum = 0<br>
for j in i..len(A):<br>
cur_sum += A[j]<br>
if cur_sum > max_sum:<br>
max_sum = cur_sum<br>
max_i = i<br>
max_j = j<br>
return (max_i, max_j, max_sum)
</code>
</p></dd>
<dt><b>Question 4.1-3: </b><p>Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?</p></dt>
<dd><p><em>This question asks a question that is specific to the implementation, and the computer on which it is run. I will therefore be skipping it in this writeup.</em> It is worthwhile to note that it is almost guarenteed that changing he implementation to use the brute force method for values less than $n_0$ is very likely to change $n_0$.</p></dd>
<dt><b>Question 4.1-4: </b><p>Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?</p></dt>
<dd><p>For the brute force algorithm it would be rather trivial to add a check, and if the return max_sum is > 0 return the empty array.</p>
<p>For the recursive divide and conquer algorithm is is sufficient to just change the $\textit{Find-Max-Crossing-Subarray}$ in a manner similar to the brute force method. If $\textit{Find-Max-Crossing-Subarray}$ return the correct value, then $\textit{Find-Maximum-Subarray}$ will do the correct thing.</p></dd>
<dt><b>Question 4.1-5: </b><p>Develop a nonrecursive linear-time algorithm for the maximum-subarray problem.<sup><small><a href="#clrs_4_1_q5">[1]</a></small></sup></p></dt>
<dd><p>If one knows a previous answer to the max-subarray problem for a given prefix of the array than any new element consists of only two cases: being part of the maximum subarray or not being part of the maximum subarray. It is easier to explain with pseudocode:
<code style="background-color: #f2f2f2; display: block;">
max_start = 0<br>
max_end = 0<br>
max_sum = A[0]<br>
<br>
max_with_j = A[0]<br>
for j in 1..len(A):<br>
# If J is in a maximum-subarray, either j is going to being the maximum on its, or it will will add to the current max</br>
max_with_j = max(A[j], max_with_j + x)<br>
Determine if J is in a maximum-subarray<br>
if max_with_j >= max_sum:<br>
max_sum = max_with_j<br>
max_end = j<br>
#Set the starting value if j is the sole element of a new subarray<br>
if max_with_j == A[j]:<br>
max_start = j<br>
return (max_start, max_end, cur_max)
</code>
</p></dd>
</dl>
<small>
<ol>
<li><a name="clrs_4_1_q5"></a>The question provides some hints as to the solution of the problem.</li>
</ol>
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-48186693654192923762015-03-29T21:23:00.001-07:002015-03-29T23:12:20.168-07:00FreeBSD SMB Client under OSX Host<p>I recently purchased a new Macbook Pro and wanted to get a FreeBSD Virtual Machine set up in order to continue doing development work on it. Unfortunately, FreeBSD as a guest does not support native folder sharing so I decided to try using a samba mounted.</p>
<p>I decided to set up my VM to have two network interfaces: a NATed interface for internet access and a host-only interface for access to SMB and ssh.</p>
<p>The NAT networking configuration looks like:</p>
<pre>
NetworkName: FreeBSDNatNetwork
IP: 10.0.2.1
Network: 10.0.2.0/24
IPv6 Enabled: Yes
IPv6 Prefix:
DHCP Enabled: Yes
Enabled: Yes
Port-forwarding (ipv4)
SSH IPv4:tcp:[]:5022:[10.0.2.4]:22
Port-forwarding (ipv6)
FreeBSD ssh:tcp:[]:6022:[fd17:625c:f037:2:a00:27ff:fefc:9dab]:22
loopback mappings (ipv4)
</pre>
<p>The Host-Only networking configuration looks like:</p>
<pre>
Name: vboxnet0
GUID: 786f6276-656e-4074-8000-0a0027000000
DHCP: Disabled
IPAddress: 192.168.56.1
NetworkMask: 255.255.255.0
IPV6Address:
IPV6NetworkMaskPrefixLength: 0
HardwareAddress: 0a:00:27:00:00:00
MediumType: Ethernet
Status: Up
VBoxNetworkName: HostInterfaceNetworking-vboxnet0
</pre>
The FreeBSD configuration looks like this:
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1Qs2vLfJk-9HGyPPHx-Qc7hNDXH5BYEQXuwpyYztRxtBAj_zqOJYBqwb4YCY2wez8Qio6A-Svtb9Dkr7vhuB1gYdi96u6i4wu-iwtAoG2rvakgUc7jyf9aoGyUdfc7OK2kKorWl75JV3l/s1600/FreeBSD+em0+inet+config.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi1Qs2vLfJk-9HGyPPHx-Qc7hNDXH5BYEQXuwpyYztRxtBAj_zqOJYBqwb4YCY2wez8Qio6A-Svtb9Dkr7vhuB1gYdi96u6i4wu-iwtAoG2rvakgUc7jyf9aoGyUdfc7OK2kKorWl75JV3l/s1600/FreeBSD+em0+inet+config.png" /></a>
The OSX sharing configuration looks like:
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg3cqgi1g7Y20rucETaA3Umf2gf-IMkzEnXcPrTo2ATnmy59oxiod9H__m2FumdTxIR5zPCGXG-gX10LewiziXZs_4x_2QmfNYlpnK3z7A7tIQlvsOaKEnv8wSvm1ZWF30hLAmmmRtPIXgw/s1600/OSX+Sharing+FreeBSD+SMB.png" imageanchor="1" ><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg3cqgi1g7Y20rucETaA3Umf2gf-IMkzEnXcPrTo2ATnmy59oxiod9H__m2FumdTxIR5zPCGXG-gX10LewiziXZs_4x_2QmfNYlpnK3z7A7tIQlvsOaKEnv8wSvm1ZWF30hLAmmmRtPIXgw/s1600/OSX+Sharing+FreeBSD+SMB.png" /></a>
<p>Unfortunately, when attempting to actually mount the SMB filesystem with:
<code>mount_smbfs -I 192.168.56.1 //eax@192.168.56.1/shared_vbox</code> I get the error <code>mount_smbfs: can't get server address: syserr = Operation timed out</code></p>
<p>I tried installing the package <code>net/samba36</code> and found that I needed the <code>--signing=off</code> flag to let it work: <img src="https://www.dropbox.com/s/7np7kzeob93q74c/working%20smbclient%20without%20signing.png?dl=1"></p>
<p>It seems based on this setup and research that <a href="https://www.freebsd.org/">FreeBSD</a> can not natively mount an OSX samba share. It might be possible to use <code>sysutils/fusefs-smbnetfs</code>. Other people have recommended NFS or sshfs.</p>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-73891161212524425192013-11-03T21:43:00.000-08:002013-11-03T21:56:18.250-08:00Two Factor Authentication for SSH (with Google Authenticator)<p>Two factor authentication is a method of ensuring that a user has a physical device in addition to their password when logging in to some service. This works by using a time (or counter) based code which is generated by the device and checked by the host machine. Google provides a service which allows one to use their phone as the physical device using a <a href="https://play.google.com/store/apps/details?id=com.google.android.apps.authenticator2&hl=en">simple app</a>.</p>
<p>This service can be easily configured and greatly increases the security of your host.</p>
<p>
<h4>Installing Dependencies</h4>
<ol>
<li>There is only one: the Google-Authenticator software itself:
<pre># pkg install pam_google_authenticator</pre></li>
On older FreeBSD intallations you may use:
<pre># pkg_add -r pam_google_authenticator</pre>
On Debian derived systems use:
<pre># apt-get install libpam-google-authenticator</pre>
</li>
</ol>
<h4>User configuration</h4>
Each user must run "google-authenticator" once prior to being able to login with ssh. This will be followed by a series of yes/no prompts which are fairly self-explanatory.
Note that the alternate to time-based is to use a counter. It is easy to lose track of which number you are at so most people prefer time-based.
<ol start="2">
<li>
<pre>$ google-authenticator
Do you want authentication tokens to be time-based (y/n)
...
</pre>
Make sure to save the URL or secret key generated here as it will be required later.
</li>
</ol>
<h4>Host Configuration</h4>
To enable use of Authenticator the host must be set up to use PAM which must be configured to prompt for Authenticator.
<ol start="3">
<li>
Edit the file /etc/pam.d/sshd and add the following in the "auth" section prior to pam_unix:
<blockquote>
auth requisite pam_google_authenticator.so
</blockquote>
</li>
<li>Edit /etc/ssh/sshd_config and uncomment <blockquote>ChallengeResponseAuthentication yes</blockquote>
</li>
</ol>
<h4>Reload ssh config</h4>
<ol start="5">
<li>Finally, the ssh server needs to reload its configuration:
<pre># service sshd reload</pre></li>
</ol>
<h4>Configure the device</h4>
<ol start="6">
<li>
Follow the <a href="https://support.google.com/accounts/answer/1066447?hl=en">instructions provided</a> by Google to install the authentication app and setup the phone.
</li>
</ol>
<p>That is it. Try logging into your machine from a remote machine now</p>
<small>Thanks bcallah for proof-reading this post.</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-30233835752321699532013-04-28T18:37:00.000-07:002018-02-17T02:24:30.730-08:00Pre-Interview NDAs Are Bad<p>I get quite a few emails from business folk asking me to interview with them or forward their request to other coders I know. Given the volume it isn't feasible to respond affirmatively to all these requests.</p>
<p>If you want to get a coder's attention there are a lot of things you could do, but there is one thing you shouldn't do: require them to sign an NDA before you interview them.</p>
<p>From the candidates point of view:</p>
<ol>
<li>There are a lot more ideas than qualified candidates.</li>
<li>Its unlikely your idea is original. It doesn't mean anyone else is working on it,
just that someone else probably thought of it.</li>
<!--<li>It introduces liability. Say the candidate was with your competitors
when they signed an NDA with you. Now the other companies are less likely
to give her offers and may even rescind existing offers because of the
possible liability.</li>-->
<li>Lets say the candidate was working on a similar, if not identical project.
If the candidate fails to continue with you now they have to consult a
lawyer to make sure you can't sue them for a project they were working
on before</li>
<li>NDAs are hard legal documents and shouldn't be signed without
consulting a lawyer. Does the candidate really want to find a lawyer
before interviewing with you?</li>
<li>An NDA puts the entire obligation on the candidate.
What does the candidate get from you?</li>
</ol>
From a company founders point of view:
<ol start="6">
<li>Everyone talks about the companies they interview with to someone.
Do you want to be that strange company which made them sign an NDA?
It can harm your reputation easily.</li>
<li>NDAs do not stop leaks. They serve to create liability when a leak
occurs. Do you want to be the company that sues people that interview
with them?</li>
</ol>
<p>There are some exceptions; for example government and security jobs may require security clearance and an NDA. For those jobs it is possible to determine if a coder is qualified and a good fit without disclosing confidential company secrets.</p>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-80755732289223509272012-12-21T14:23:00.000-08:002013-01-04T08:40:28.311-08:00Correctly Verifying an Email Address<p>Some services that accept email addresses want to ensure that these email addresses are valid.</p>
There are multiple aspects to an email being valid:
<ol>
<li>The address is syntactically valid.</li>
<li>An SMTP server accepts mail for the address.</li>
<li>A human being reads mail at the address.</li>
<li>The address belongs to the person submitting it.</li>
</ol>
<p>How does one verify an email address? I'll start with the wrong solutions and build up the correct one.</p>
<h3>Possibility #0 - The Regular Expression</h3>
<p>Discussions on a correct regular expression to parse email addresses are endless. They are almost always wrong. Even really basic pattern matching such as *@*.* is wrong: it will reject the valid email address n@ai.<sup>[5]</sup></p>
<p>Even a fully correct regular expression does not tell you if the mailbox is valid or reachable.
<p>This scores 0/4 on the validity checking scale.</p>
<h3>Possibility #1 - The VRFY Command</h3>
<p>The oldest mechanism for verifying an email address is the VRFY mechanism in <a href="https://tools.ietf.org/html/rfc821">RFC821</a> section 4.1.1:</p>
<blockquote cite="https://tools.ietf.org/html/rfc821">
VERIFY (VRFY)
This command asks the receiver to confirm that the argument identifies a user. If it is a user name, the full name of the user (if known) and the fully specified mailbox are returned.</blockquote>
<p>However this isn't sufficient. Most SMTP servers disable this feature for security and anti-spam reasons. This feature could be used to enumerate every username on the server to perform more targeted password guessing attacks:</p>
<blockquote cite="https://tools.ietf.org/html/rfc2505#section-2.11">
Both SMTP VRFY and EXPN provide means for a potential spammer to test whether the addresses on his list are valid (VRFY)... Therefore, the MTA SHOULD control who is is allowed to issue these commands. This may be "on/off" or it may use access lists similar to those mentioned previously.
</blockquote>
<p>This feature wasn't guaranteed to be useful at the time the RFC was written:<sup>[1]</p>
<blockquote cite="https://tools.ietf.org/html/rfc821">The VRFY and EXPN commands are not included in the minimum implementation (Section 4.5.1), and are not required to work across relays when they are implemented.</blockquote>
<p>Finally, even if VRFY was fully implemented there is no guarantee that a human being reads the mail sent to that particular mailbox.</p>
<p>All of this makes VRFY useless as a validity checking mechanism so it scores 1/4 on the validity checking scale.</p>
<h3>Possibility #2 - Sending a Probe Message</h3>
<p>With this method you try to connect with a mail server and pretends to send a real mail message but cut off before sending the message content. This is wrong for a for the following reasons:</p>
<p>A system administrator that disabled VRFY has a policy of not allowing for the testing for email addresses. Therefore the ability to test the email address by sending a probe should be considered a bug and must not be used.</p>
<p>The system might be set up to detect signs up of a probe such as cutting off early may rate limit or block the sender.</p>
<p>In addition, the SMTP may be temporarily down or the mailbox temporarily unavailable but this method provides no resilience against failure. This is especially true if this mechanism is attempting to provide real-time feedback to the user after submitting a form.</p>
<p>This scores 1/4 on the validity checking scale.</p>
<h3>Possibility #3 - Sending a Confirmation Mail</h3>
<p>If one cares about if a human is reading the mailbox the simplest way to do so is send a confirmation mail. In the email include a link to a website (or set a special reply address) with some indication of what is being confirmed. For example, to confirm "<b>user@example.com</b>" is valid the link might be http://example.com/verify?<b>email=user@example.com</b> or http://example.com/verify?<b>account=12345</b><sup>[2]</sup>.
<p>This method is resilient against temporary failures and forwarders. Temporary failures could be retried like a normal SMTP conversation.</p>
<p>This way it is unlikely that a non-human will trigger the verification email<sup>[3]</sup>. This approach solves some of the concerns, it suffers from a fatal flaw:</p>
<p>It isn't secure. It is usually trivial to guess the ID number, email account, other identifier. An attacker could sign up with someone else's email account and then go to the verification page for that user's account. It might be tempting to use a random ID but randomness implementations are usually not secure.</p>
<p>This scores 3/4 on the validity checking scale</p>
<h3>Possibility #4 - Sending a Confirmation Mail + HMAC</h3>
<p>The correct solution is to send a confirmation, but include a <a href="https://en.wikipedia.org/wiki/Message_authentication_code">MAC</a> of the identifier in the verification mechanism (reply, or url) as well. A MAC is a construction used to authenticate a message by combining a secret key and the message contents. One family of constructions, HMAC, is a particularly good choice. This way the url might become http://example.com/verify?email=<b>user@example.com&mac=74e6f7298a9c2d168935f58c001bad88</b><sup>[4]</sup></p>
<p>Remember that the HMAC is a specific construction, not a naive hash. It would be wise to use a framework native function such as PHP's hash_hmac. Failing to include a secret into the construction would make the MAC trivially defeated by brute force.
<p>This scores 4/4 on the validity checking scale</p>
<h3>Closing Notes</h3>
<p>Getting email validation right is doable, but not as trivial as many of the existing solutions make it seem.
<small>
<ol>
<li>Note that <a href="https://tools.ietf.org/html/rfc1123">RFC1123</a> more specifically spells out that VRFY MUST be implemented but MAY be disabled.</li>
</li>
<li>This is not my luggage password.</li>
<li>It is still possible for a auto-reply bot to trigger reply based verification schemes. Bots that click every link in received email are uncommon.</li>
<li>This is HMAC-MD5. It isn't insecure as collisions aren't important for HMAC. I chose it because it is short.</li>
<li><a href="mailto:n@ai">n@ai</a> is a in-use email address by a person named Ian:
<pre>%dig +short ai MX
10 mail.offshore.ai.</pre>
</li>
</ol>
Thank you to bd for proofreading and reviewing this blog post.
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-58364997126522750642012-11-21T20:54:00.000-08:002013-02-12T21:26:43.955-08:00Don't Use Timing Functions for Profiling<p>One common technique for profiling programs is to use the gettimeofday system call (with code that looks something like this):</p>
<details>
<summary>Example (incorrect) code that uses gettimeofday - click to view</summary>
<code><pre class="prettyprint">#include <time.h>
#include <stdlib.h>
#include <stdio.h>
void function(void)
{
struct timeval before;
struct timeval after;
gettimeofday(&before, NULL);
codetoprofile();
gettimeofday(&after, NULL);
time_t delta = after.tv_sec - before.tv_sec;
printf("%ld\n",delta);
}</pre>
</code>
</details>
<p>However, using <a href="http://pubs.opengroup.org/onlinepubs/009695399/functions/gettimeofday.html">gettimeofday</a>(2) or <a href="http://pubs.opengroup.org/onlinepubs/009695399/functions/time.html">time</a>(3) or any function designed to get a time of day to obtain profiling information is wrong for many reasons:</p>
<ol>
<li>Time can go backwards. In a virtualized environment this can happen quite often. In non-virtualized environments this can happen due to time zones. Even passing CLOCK_MONOTONIC to clock(3) doesn't help as it can go backwards during a leap second expansion.</li>
<li>Time can change drastically for no reason. Systems with NTP enabled periodically sync their time with a time source. This can cause the system time to change by minutes, hours, or even days! </li>
<li>These functions measure <i>Wall Clock</i> time. Time spent on entirely unrelated processes is going to be included in the profiling data!</li>
<li>Even if you have disabled everything else on the system<small><sup>[1]</sup></small> the delta computed above includes both of <i>User time</i> and <i>System Time</i>. If your algorithm is very fast but the kernel has a slow implementation of some system call you won't learn much.</li>
<li>gettimeofday relies on the cpu clock which may differ across cores resulting in time skew.</li>
</ol>
<p>So what should be used instead?</p>
<p>There isn't a good, portable, function to obtain profiling information. However there are options for those not tied to a particular system (or those willing to maintain multiple implementations for different systems.</p>
<p>The <a href="http://www.freebsd.org/cgi/man.cgi?query=getrusage">getrusage</a>(2) system call is one option for profiling data. This provides different fields for user time (<i>ru_utime</i>) and system time (<i>ru_stime</i>) at a relatively high level of precision and accuracy.</p>
<p>Using DTraces <a href="https://wikis.oracle.com/display/DTrace/profile+Provider
">profiling provider</a> also seems to be a decent choice although I limited experience with it.</p>
<p>Finally, using APIs meant to access hardware specific features such as FreeBSD's <a href="http://www.freebsd.org/cgi/man.cgi?query=hwpmc&sektion=4">hwpmc</a> is likely to provide the best results at the cost of being the least portable. Linux has similar features such as <a href="http://oprofile.sourceforge.net/">oprofile</a> and <a href="https://perf.wiki.kernel.org/index.php/Main_Page">perf</a>. Using dedicated profilers such as Intel's <a href="http://software.intel.com/en-us/intel-vtune-amplifier-xe">vtunes</a><small><sup>[2]</sup></small> may also be worthwhile.</p>
<small>
<ol>
<li>Including networking, background process swapping, cron, etc.</li>
<li>A <a href="http://wiki.freebsd.org/VTune">FreeBSD version</a> is available.</li>
</ol>
<b>update 2012-11-26:</b> Include note about clock skew across cores.<br>
<b>Update 2013-02-13:</b> Update and fix a massive error I had w.r.t. clock(3)
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-35414935297084316532012-10-31T08:41:00.001-07:002014-09-02T20:56:42.024-07:00Finding the majority element in a stream of numbersSome time ago I came across the following question.<br />
<blockquote>
As input a finite stream stream of numbers is provided.
Define an algorithm to find the majority element of the input.
The algorithm need not provide a sensible result if no majority element exists.
You may assume a transdichotomous memory model.</blockquote>
There are a few definitions which may not be immediately clear:
<br />
<dl>
<dt>Stream</dt>
<dd>A possibly infinite set of data which may not be reused in either the forward or backward direction without explicitly storing it.</dd>
<dt>Majority element</dt>
<dd>An element in a set which occurs more than half the time.</dd>
<dt>Transdichotomous</dt>
<dd>The integer size is equal to the word size of memory. One does not need to worry about storing partial pieces of integers in separate memory units.</dd>
</dl>
Unfortunately this answer isn't of my own invention, but it is interesting and succinct.<br />
<br />
<details>
<summary>The algorithm (click to view)</summary>
Using 3 registers the <i>accumulator</i>, the <i>guess</i> and the current element (<i>next</i>):
<ol>
<li>Initialize <i>accumulator</i> to 0</li>
<li>Accept the next element of the stream and place it into <i>next</i>. If there are no more elements go to step #7.</li>
<li>If <i>accumulator</i> is 0 place <i>next</i> into <i>guess</i> and increment <i>accumulator</i>.</li>
<li>Else if <i>guess</i> matches <i>next</i> increment <i>accumulator</i></li>
<li>Else decrement <i>accumulator</i>
</li>
<li>Go to step 2</li>
<li>Return the value in <i>guess</i> as the result</li>
</ol>
</details>
<br />
An interesting property of this algorithm is that it can be implemented in $O(n)$ time even on a single tape Turing Machine.Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-12413353112182515072012-10-30T12:08:00.002-07:002012-10-31T07:45:45.209-07:00Cneonction: closed HTTP header<p>When you make a request to certain websites you may find an unusual header that looks a little strange:</p>
<blockquote>
<pre>
[8000 eitan@radar ~ ]%curl -I http://www.imdb.com/ 2>/dev/null|grep close
Cneonction: close
[8001 eitan@radar ~ ]%curl -I http://maps.apple.com/ 2>/dev/null|grep close
Cneonction: close
</pre>
</blockquote>
<p>This isn't a typo though. Some load balancers that sit between the web server and end user want to implement <a href="https://en.wikipedia.org/wiki/HTTP_persistent_connection">HTTP keep-alive</a> without modifying the back end web server. The load balancer therefore has to add "Connection: Keep-Alive" to the HTTP header and also has to elide the "Connection: close" from the real webserver. However, if it completely removes the line the load balancer (acting as a TCP proxy) would have to stall before forwarding the complete text in order to recompute the TCP checksum. This increases latency on packet delivery.</p>
<p>Instead, the proxy uses a hack to keep the checksum unchanged. The TCP checksum of a packet is the 1s complement summation of all the 16 bit words (the final word might be right padded with zeros).<sup>[1]</sup> By manipulating the ordering, but not the content of the header the proxy can avoid changing the TCP checksum except by the fixed amount that the "Connection: Keep-Alive" adds (2061).</p>
<p>In particular:</p>
<pre>
>>><code class="prettyprint">sum(ord(i) for i in "Connection") - sum(ord(i) for i in "Cneonction")
</code>
0
</pre>
<p>This reordering also keeps the packet size the same.</p>
<small>
<ol>
<li><a href="https://tools.ietf.org/html/rfc793#section-3.1">RFC793</a></li>
</ol>
<b>Edit 2012-10-31: </b> Make the RFC a link and remove pointless "2>&1"<br/>
Thanks abbe for the inspiration! Thanks wxs for the proofreading.
</small>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com1tag:blogger.com,1999:blog-7029605438334875741.post-13810340564020808742012-10-09T07:49:00.003-07:002012-10-10T05:08:47.322-07:00Reduced Entropy in rand() and random()<b>TL;DR:</b> Don't rely on undefined behavior, even when you think it <em>should</em> work.
<hr>
<p>I recently reported a minor issue to the <a href="http://freebsd.org">FreeBSD</a> security team.</p>
<p>The libc random functions had code<sup>1,2</sup> designed to run when /dev/random is not available. This can easily occur in a chroot or jail environment.</p>
<pre>
<code class="prettyprint">if (!done) {
struct timeval tv;
unsigned long junk;
gettimeofday(&tv, NULL);
srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk);
return;
}</code>
</pre>
<p>This code is designed provide a minimal amount of entropy in the "failure" case. Unfortunately, it doesn't even provide the entropy it claims to. This is a minor issue because getpid, getimeday, and a single long variable don't provide a lot of entropy in the first place: (only $log_2{sizeof(long)}$ bits).</p>
<p>The point of the <code>junk</code> value is to add entropy by using uninitialized
memory. This relies on the compiler being "stupid" enough not optimize it away.<p>
<p>Unfortunately clang and newer versions of gcc are smart
enough to use the undefined behavior in undesired ways.</p>
<p>clang <sup>3</sup> removes any computation which relies on the undefined behavior and so produces the following object code:</p>
<code>
<pre>
af0: e8 5f fc ff ff callq 754 <gettimeofday@plt>
af5: e8 7a fc ff ff callq 774 <getpid@plt>
afa: e8 65 fc ff ff callq 764 <srandom@plt>
</pre>
</code>
<p>Note that the junk variable is entirely unused and that the <code>xor</code> operation between gettimeofday and getpid is non-existent.
<p>gcc 4.6 <sup>4</sup> outputs:</p>
<code>
<pre>
ce8: e8 03 fa ff ff callq 6f0 <gettimeofday@plt>
ced: e8 4e fa ff ff callq 740 <getpid@plt>
cf2: 48 8b 7c 24 08 mov 0x8(%rsp),%rdi
cf7: 48 33 3c 24 xor (%rsp),%rdi
cfb: c1 e0 10 shl $0x10,%eax
cfe: 48 98 cltq
d00: 48 31 c7 xor %rax,%rdi
d03: e8 28 fa ff ff callq 730 <srandom@plt>
</pre>
</code>
Note that in this case the junk value appears to be <code>(%rsp)</code> which isn't all that random.
<p>gcc 4.2<sup>5</sup> produces the following code</p>
with the junk variable
<code>
<pre>
d9f: e8 18 fa ff ff callq 7bc <gettimeofday@plt>
da4: e8 43 fa ff ff callq 7ec <getpid@plt>
da9: 48 8b 3c 24 mov (%rsp),%rdi
dad: 48 33 7c 24 08 xor 0x8(%rsp),%rdi
db2: c1 e0 10 shl $0x10,%eax
db5: 48 98 cltq
db7: 48 31 c7 xor %rax,%rdi
<b> dba: 48 31 df xor %rbx,%rdi</b>
dbd: e8 1a fa ff ff callq <srandom@plt>
</pre>
</code>
and without:
<code>
<pre>
d9f: e8 18 fa ff ff callq 7bc <gettimeofday@plt>
da4: e8 43 fa ff ff callq 7ec <getpid@plt>
da9: 48 8b 3c 24 mov (%rsp),%rdi
dad: 48 33 7c 24 08 xor 0x8(%rsp),%rdi
db2: c1 e0 10 shl $0x10,%eax
db5: 48 98 cltq
db7: 48 31 c7 xor %rax,%rdi
dba: e8 1d fa ff ff callq 7dc <srandom@plt>
</pre>
</code>
<p>The base version of gcc isn't vulnerable. However, with the upcoming switch to the clang compiler the FreeBSD does become vulnerable.<p>
<p>The first proposed fix was to add the <code>volatile</code> type qualifier to the junk variable. <s>While this seemed to fix the code generation issue I didn't believe this to be a valid fix as the behavior is still undefined<sup>6</sup></s> (I misread text of the standard). Additionally, the value is likely have be very predictable. A preference was expressed to remove the junk variable as using it may leak a small amount of stack data.</p>
<p>I proposed the simple and obvious fix of removing the use of the junk variable<sup>7</sup></p>
<p>In a brief survey of other libraries I noticed similar issues. I will attempt to notify the vendors</p>
<p>It should be obvious, but undefined behavior is <em>undefined</em> and can't be relied on to ever to give a sensible result.
<small>
<ol>
<li><a href="http://svnweb.freebsd.org/base/head/lib/libc/stdlib/random.c?revision=165903&view=markup">random.c r165903</a> (line 316)</li>
<li><a href="http://svnweb.freebsd.org/base/head/lib/libc/stdlib/rand.c?view=markup&pathrev=241046">rand.c r241046</a> (line 131)</li>
<li>FreeBSD clang version 3.1 (branches/release_31 156863) 20120523 compiled with -O2 or -O3</li>
<li>gcc46 (FreeBSD Ports Collection) 4.6.4 20120608 (prerelease) compiled with -O2</li>
<li>gcc (GCC) 4.2.1 20070831 patched [FreeBSD] compiled with -O3</li>
<li>sections 5.1.2.2.3 and 6.7.2.4 of ISO9899</li>
<li><a name="fbsd_rand_bug_7" href="http://svnweb.freebsd.org/base?view=revision&revision=241373">svn commit r241373</a></li>
</ol>
</small>
<small>
<b>Edit 2010-10-10:</b> update the paragraph referring to undefined behavior of volatile.
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-16474523128716380882012-10-08T19:16:00.002-07:002012-10-09T07:56:04.053-07:00NFS Mount Network Booting VirtualBox<p>In order to test modifications to the <a href="http://freebsd.org">FreeBSD</a> kernel, I would like to boot a diskless virtual machine. The goal is to be able to quickly test changed I make without needing to recreate the VM each time, or run the installation procedure inside of the VM.</p>
<p>You can elect to put the root anywhere you want. For this example, I will be using /home/vm as the root of the virtual machine.</p>
<p>There are a few aspects to this:</p>
<ul>
<li>The filesystem that will be booted.</li>
<li>VirtualBox setup</li>
<li>Virtual machine setup</li>
<li>DHCP server</li>
<li>Host setup</li>
</ul>
<h4>Filesystem Installation</h4>
<ol>
<li>Create the distribution:
<pre>
cd /usr/src
make installworld installkernel distribution DESTDIR=/home/vm
</pre>
</li>
<li>
Create the /conf directory used for diskless boot. See /etc/rc.initdiskless for details.</br>
<pre>
# cd /home/vm/
# mkdir -p conf/base/etc
# cd conf/base/etc
# cat diskless_remount
/etc
# cat fstab
md /tmp mfs -s=30m,rw 0 0
md /var mfs -s=30m,rw 0 0
# cat md_size
256m
</pre>
</li>
</ol>
<h4>VirtualBox Setup</h4>
<p>Create a "host-only" interface with DHCP disabled. To do this:</p>
<ol style="overflow: hidden;">
<li>Open up the preferences screen and go the "network" tab.<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNiQKtuFZgN04GQHJHasUupxkYw_XxLwihV1XQVkyPUE8uwNt1WUW_Jb4GJnq40-kolb3caY0awEMnq1-NKJVDblFhMjYumypkbOx-L3EURqqlR6H6FV_2fqdZsPr78-cEuXGs1bj1EWY0/s1600/a1-0-prefsscreen.png" imageanchor="1" style=""><img border="0" height="238" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiNiQKtuFZgN04GQHJHasUupxkYw_XxLwihV1XQVkyPUE8uwNt1WUW_Jb4GJnq40-kolb3caY0awEMnq1-NKJVDblFhMjYumypkbOx-L3EURqqlR6H6FV_2fqdZsPr78-cEuXGs1bj1EWY0/s320/a1-0-prefsscreen.png" alt="screenshot of the preferences screen"/></a></li>
<li>Create a new host-only network (the green plus on the right).<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaGsomdGjhPnJPVachLaOkRx0uak7YM7iQo4MWnZdw-oZFHcJYw0RH8TzmZPW28KPyDiP-JYJoFfIKl9i_7_vjJPujwwxf_g3MnZJq5NkHWnaIwqtnMADvGLFgAUiJfXMyhvHoJ76fU4lU/s1600/a2-host-only-networks.png" imageanchor="1" style=""><img border="0" height="281" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaGsomdGjhPnJPVachLaOkRx0uak7YM7iQo4MWnZdw-oZFHcJYw0RH8TzmZPW28KPyDiP-JYJoFfIKl9i_7_vjJPujwwxf_g3MnZJq5NkHWnaIwqtnMADvGLFgAUiJfXMyhvHoJ76fU4lU/s320/a2-host-only-networks.png"
alt="screenshot of the network preferences screen"/></a>
</li>
<li>Disable the DHCP Server.<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikM0kxzDP5nks35LvZvb1WtMLAIxqh_oMGqns5sUZGCeNja14_SRyl8BPrc4doLcpqDCwk_RgAZQwrFa8EMaX4XUd_BCrGHRF0I-PFlS-xb_ZlwSRMFDbWaoM6wqC-Sw4ZwRiHG3MRIZFt/s1600/a3-no-dhcp.png" imageanchor="1" style=""><img border="0" height="163" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEikM0kxzDP5nks35LvZvb1WtMLAIxqh_oMGqns5sUZGCeNja14_SRyl8BPrc4doLcpqDCwk_RgAZQwrFa8EMaX4XUd_BCrGHRF0I-PFlS-xb_ZlwSRMFDbWaoM6wqC-Sw4ZwRiHG3MRIZFt/s320/a3-no-dhcp.png" alt="screenshot of the host only network DHCP screen" /></a>
</li>
<li>Select an IP Address in the range your VM will have.<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEYmezbO_Y8DNDPF39TFPgOiMsn7IY3RGA4CSb-MVQZv6wlfvxEVyoGQRlhFz81_aqJWK9XvMC_7JVQCMXFXh2AL-bV51DTKgWm_N73DR3wa0nyUSKfjLcsVJ4F8bGJcIlWPvSCdWw1aHp/s1600/a4-note-the-ip-addr.png" imageanchor="1" style=""><img border="0" height="163" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjEYmezbO_Y8DNDPF39TFPgOiMsn7IY3RGA4CSb-MVQZv6wlfvxEVyoGQRlhFz81_aqJWK9XvMC_7JVQCMXFXh2AL-bV51DTKgWm_N73DR3wa0nyUSKfjLcsVJ4F8bGJcIlWPvSCdWw1aHp/s320/a4-note-the-ip-addr.png" alt="screenshot of the host only network preferences screen" /></a>
</li>
<li>Note that the DHCP server will continue to run until killed or the machine rebooted:
<pre>
## Note that you may kill too much here. Be careful.
# pgrep -fl DHCP
# pkill -15 DHCP
</pre>
</li>
</ol>
<h3>Create the Virtual Machine</h3>
<ol>
<li>Create a new virtual machine. Make sure to select "FreeBSD - 64 bit". Note that you should create this machine without any disk (and ignore the warning at the end).<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhoEwKizSQ2hTBzBi98uYyB6yejAJwUWruJTNPyPxYoPb_inXSwllXP-Z-5E9VtYD_772cuWZ32oqvDVprX-A7FefzgpmDQk1tnp7RMqj04xh71cvvFaSK7kHyvbx66Y-_r7pBXA8QdDRV4/s1600/b2-select-64-bit.png" imageanchor="1" style=""><img border="0" height="195" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhoEwKizSQ2hTBzBi98uYyB6yejAJwUWruJTNPyPxYoPb_inXSwllXP-Z-5E9VtYD_772cuWZ32oqvDVprX-A7FefzgpmDQk1tnp7RMqj04xh71cvvFaSK7kHyvbx66Y-_r7pBXA8QdDRV4/s320/b2-select-64-bit.png" alt="filled in machine name and type screenshot" /></a>
</li>
<li>Open up the virtual machine's settings<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixn8YAx56R2KtdAFMUVkcBxVyy0Bw-vjddTRysQAYSqM5v8WB4gFodQYqv7EBvACGj06BbSqsNddhgx5gNri_YI4KYKan6S84PY6Z1eV1uq7Lq6XoJ13CmuTMIELSZBrGesL8jmcjiM0Sg/s1600/c1-the-vm-settings-screen.png" imageanchor="1" style=""><img border="0" height="228" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEixn8YAx56R2KtdAFMUVkcBxVyy0Bw-vjddTRysQAYSqM5v8WB4gFodQYqv7EBvACGj06BbSqsNddhgx5gNri_YI4KYKan6S84PY6Z1eV1uq7Lq6XoJ13CmuTMIELSZBrGesL8jmcjiM0Sg/s320/c1-the-vm-settings-screen.png" alt="default settings screenshot" /></a>
</li>
<li>Select only the "Network" option under boot order (System->Motherboard->Boot Order). Also check "Hardware clock in UTC time."<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkj0Vi9sWpdPx7KWVLJwYz8DUQ4VhngsDeOMVSGZzRkDfI65g0wTxSr1dveVvIDE6_rt2fgJe-BP3xGDyIDJb1knwIskfMn5DK842iP_Khkq2XSa583tFVxQtyBwjDlC3CviY2qtDgeorn/s1600/c2-select-network-and-utc-clock.png" imageanchor="1" style=""><img border="0" height="228" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhkj0Vi9sWpdPx7KWVLJwYz8DUQ4VhngsDeOMVSGZzRkDfI65g0wTxSr1dveVvIDE6_rt2fgJe-BP3xGDyIDJb1knwIskfMn5DK842iP_Khkq2XSa583tFVxQtyBwjDlC3CviY2qtDgeorn/s320/c2-select-network-and-utc-clock.png" alt="changed setting screen screenshot"/></a>
</li>
<li>Under network select the Host Only Adapter created before. Under advanced options, change the adapter type to "PCNet-PCI II." Also make a note of the mac address of the virtual machine. It will be needed later.<br/>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiPgxAfJVpKQAUsqAr4yJEFYhfp1yHjrG19Ai41fbpFzt9xFT1N366uH3qN0GT1XGJm_Q_k9GG9w7VsjKwTwfZ5DgrjF9SW4HrhwDyw6k0O3wG1WrMi3RghZQRpKQFENdyqF-iwLqbv_y88/s1600/c3-select-hostonly-and-pcnet-pci-ii.png" imageanchor="1" style=""><img border="0" height="228" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiPgxAfJVpKQAUsqAr4yJEFYhfp1yHjrG19Ai41fbpFzt9xFT1N366uH3qN0GT1XGJm_Q_k9GG9w7VsjKwTwfZ5DgrjF9SW4HrhwDyw6k0O3wG1WrMi3RghZQRpKQFENdyqF-iwLqbv_y88/s320/c3-select-hostonly-and-pcnet-pci-ii.png" alt="changed network setting screen screenshot"/></a>
</li>
</ol>
<h3>DHCP Server</h3>
For simplicity I opted to use a really simple DHCP server <a href="http://www.thekelleys.org.uk/dnsmasq/doc.html">dnsmasq</a>:
<ol>
<li>Install dnsmasq<br/>
<pre>
$ make -C /usr/ports/dns/dnsmasq install clean
</pre>
</li>
<li>Configure dnsmasq to server as a tftp and DHCP server for the virtual machine interface. Modify /usr/local/etc/dnsmasq.conf (I've bolded the parts that are configuration specific):<br/>
<pre>
interface=<b>vboxnet0</b>
dhcp-range=<b>172.16.100.100,172.16.100.200,48h</b><sup>[1]</sup>
#Note that this mac address is the mac address of the vm noted earlier.
dhcp-host=<b>01:02:03:04:05:06,vm-testing,172.16.100.100</b>,set:diskless
dhcp-boot=tag:diskless,<b>/home/vm/boot/pxeboot</b>
dhcp-option=tag:diskless,option:root-path,"<b>/home/vm/</b>"
enable-tftp
</pre>
</li>
<li>Add this to /etc/dhclient.conf so that you can reference your virtual machine by name:<br/>
<pre>
precede domain-name-servers 127.0.0.1;
</pre>
</li>
</ol>
<h3>Host Setup</h3>
<ol>
<li>Add the following to /etc/rc.conf:
<pre>
# Required for VirtualBox
devfs_system_ruleset="system"
# Required for diskless boot
dnsmasq_enable="YES"
# NFS Exports
rpcbind_enable="YES"
nfs_server_enable="YES"
mountd_enable="YES"
mountd_flags="-r"
nfs_client_enable="YES"
weak_mountd_authentication="YES"
</pre>
</li>
<li>Add the directory to /etc/exports:
<pre>
<b>/home/vm</b> -ro -alldirs -network <b>172.16.0.0</b> -maproot=root
</pre>
</li>
</ol>
<p>Now you are all set. Just boot the virtual machine from VirtualBox and watch it go!</p>
<hr/>
<small>
<ol>
<li>Note that the 172.16.0.0/20 network is <a href="https://tools.ietf.org/html/rfc1918">RFC 1918</a> private address space.</li>
</ol>
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-57423343201498035262012-10-03T10:08:00.000-07:002012-12-24T15:17:02.853-08:00#!/bin/bash considered harmful<p>When one writes a shell script there are a variety of shebang lines that could be used:</p>
<ul>
<li>#!/bin/sh</li>
<li>#!/usr/bin/env bash</li>
<li>#!/bin/bash</li>
</ul>
<p>or one of many other options.</p>
<p>Of these only the first two are possibly correct.</p>
<p>Using #!/bin/bash is wrong because:</p>
<ul>
<li>Sometimes bash isn't installed.</li>
<li>If it is installed, it may not be in /bin</li>
<li>If it is in /bin, the user may have decided to set PATH to use a different installation of bash. Using an absolute path like this overrides the user's choices.</li>
<li>bash shouldn't be used for scripts intended for portability</li>
</ul>
<p>If you have bash specific code use #!/usr/bin/env bash. If you want more portable code try using Debian's <a href="http://sourceforge.net/projects/checkbaskisms/files/">checkbashism</a> to find instances of non-POSIX compliant shell scripting.</p>
<!--
<small>update 2012-12-24:</small>
<p>Some people seem to not understand why env is better than /bin/bash if bash specific operations are used. As such I'll answer from a perspective of the Unix Philosophy:</p>
<dl>
<dt>Rule of Clarity: Clarity is better than cleverness.</dt>
<dd>The error message on systems with bash not in /bin is not clear:<pre>no such file or directory: ./foo.sh</pre></dd>
<dt>Rule of Simplicity: Design for simplicity; add complexity only where you *MUST*.</dt>
<dd>If /bin/bash is hard coded into programs this forces packagers into patching the broken software. Help to eliminate downstream complexity by keeping upstream correct.</dd>
<dt>Rule of Transparency: Design for visibility to make inspection and debugging easier.</dt>
<dd>When debugging, it is often nice to quickly change the PATH in order to change the specific shell being used. A script that hard codes /bin/bash makes debugging harder.</dd>
<dt>Rule of Robustness: Robustness is the child of transparency and simplicity.</dt>
<dd>It is more robust to respect the sysadmin and the user by using env instead of hard coding the location of a shell that may not even exist</dd>
<dt>Rule of Representation: Fold knowledge into data so program logic can be stupid and robust.</dt>
<dd>If /bin/bash is hard coded and not patched out by the packager then executing the script becomes more complicated ("bash" must be explicitly prepended). Instead, it makes more sense to fold this information into data: the user's PATH.</dd>
<dt>Rule of Least Surprise: In interface design, always do the least surprising thing.</dt>
<dd>Users expect scripts to follow PATH. Ignoring the user's explicit request is very surprising.</dd>
<dt>Rule of Diversity: Distrust all claims for “one true way”.</dt>
<dd>/bin/bash represents a "one true way." Respecting the user's PATH does not</dd>
</dl>
-->Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-43221007721191594092012-10-01T07:45:00.002-07:002012-10-09T07:56:19.511-07:00Some git-svn notes<p>When working with a subversion repository I often miss the use git features. However, it is possible for git to speak the subversion protocol:</p>
<h4>Cloning the initial repository</h4>
<code>
$git svn clone svn://svn.freebsd.org/base/head<br/>
</code>
<br/><br/>
<h4>Resuming an interrupted git svn clone</h4>
<p>It is really annoying when you start a git svn clone process overnight and come back to find that it stopped in the middle. Luckily, there is a really simple way to recover - without spending hours to redownload what you already have.</p>
<code>
$git svn fetch<br/>
$git svn rebase
</code>
<br/><br/>
<h4>Committing the final patch</h4>
<p>There are a lot of workflows for this, but I prefer the cherry-pick approach:</p>
<code>
$git checkout master<br/>
$git svn rebase<br/>
$git cherry-pick <i>commit-id</i><br/>
$git svn dcommit<br/>
</code>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-31190108417485901362012-09-03T13:06:00.000-07:002012-10-31T08:44:31.494-07:00Finding the min and max in 1.5n comparisons<p>A friend of mine recently gave me the following problem:</p>
<blockquote><p>Given an unsorted set of numbers find the minimum and maximum of set in a maximum of $1.5n$ comparisons.</p></blockquote>
<p>My answer involves splitting the list up pairwise and finding the result on the only half of the set.</p>
<ol>
<li>Go through list and compare every even index to its immediate right (odd) index. Sort each pair numerically within itself. This step takes $\dfrac{1}{2}n$ comparisons.</li>
<li>Find the minimum of every odd index and find the maximum of every even element using the typical algorithm. This step takes $n$ comparisons.</li>
</ol>
<p>Note that this could be done in one pass by doing the pair comparison and the min/max comparison in one pass.</p>
<p>Is there a better way? </p>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com1tag:blogger.com,1999:blog-7029605438334875741.post-63354544322539847312012-05-07T20:47:00.001-07:002012-10-31T08:44:31.506-07:00Blogging my way through CLRS Section 11.1 (edition 2)I've taken a brief break from blogging about my Cormen readings but I decided to write up the answers to chapter 11. Note that the chapters and question numbers may not match up because I'm using an older edition of the book.
<dl><dt><b>Question 11.1-1: </b><p>Suppose that a dynamic set $S$ is represented by a direct address table $T$ of length $m$. Describe a procedure that finds the maximum element of $S$. What is the worst case performance of your procedure?</p></dt>
<dd><p>Assuming the addresses are sorted by key: Start at the end of the direct address table and scan downward until a non-empty slot is found. This is the maximum and if not:</p>
<ol><li>Initialize $max$ to $-\infty$</li>
<li>Start at the first address in the table and scan downward until a used slot is found. If you reach the end goto #5</li>
<li>Compare key to $max$. If it is greater assign it to $max$</li>
<li>Goto #2</li>
<li>Return $max$</li>
</ol>
<p>The performance of this algorithm is $\Theta(m)$. A slightly smaller bound can be found in the first case of $\Theta(m - max)$</p>
</dd>
<dt><b>Question 11.1-2: </b><p>Describe how to use a bit vector to represent a dynamic set of distinct elements with no satellite data. Dictionary operations should run in $O(1)$ time.</p></dt>
<dd>
Initialize a bit vector of length $|U|$ to all $0$s.
When storing key $k$ set the $k$th bit and when deleting the $k$th bit set it to zero. This is $O(1)$ even in a non-transdichotomous model though it may be slower.
</dd>
<br/>
<dt><b>Question 11.1-3: </b><p>Suggest how to implement a direct address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations must take $O(1)$ time.</p></dt>
<dd>
Each element in the table should be a pointer to the head of a linked list containing the satellite data. $nul$ can be used for non-existent items.
</dd>
<br/>
<dt><b>Question 11.1-4: </b><p>We wish to implement a dictionary by using direct addressing on a large array. At the start the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct address dictionary on the array. Dictionary operations should take $O(1)$ time. Using an additional stack with size proportional to the number of stored keys is permitted.</p></dt>
<dd>
<p>On insert the array address is inserted into a stack. The array element is then initialized to the value of the location in the stack.</p>
<p>On search the array element value is to see if it is pointing into the stack. If it is the value of the stack is checked to see if it is pointing back to the array.<sup><a href="#clrs_11_1_n1">[1]</a></sup></p>
<p>On delete, the array element can be set to a value not pointing the stack but this isn't required. If the element points to the value of the stack, it is simply popped off. If it is pointing to the middle of the stack, the top element and the key element are swapped and then the pop is performed. In addition the value which the top element was pointing to must be modified to point to the new location</p>
</dd>
<br/>
<dt><b>Question 11.2-1: </b><p>Suppose we have use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing what is the expected number of collisions?</p></dt>
<dd>
Since each new value is equally likely to hash to any slot we would expect $n/m$ collisions.
</dd>
<br/>
<dt><b>Question 11.2-2: </b><p>Demonstrate the insertion of the keys: $5, 28, 19, 15, 20, 33, 12, 17, 10$ into a hash table with 9 slots and $h(k) = k \mod{9}$<sup><a href="#clrs_11_1_n2">[2]</a></sup></p></dt>
<dd>
<table>
<tr>
<th>hash</th>
<th>values</th>
</tr>
<tr>
<td>1</td>
<td>28 -> 19 -> 1</td>
</tr>
<tr>
<td>2</td>
<td>20</td>
</tr>
<tr>
<td>3</td>
<td>12</td>
</tr>
<tr>
<td>5</td>
<td>5</td>
</tr>
<tr>
<td>6</td>
<td>15 -> 33</td>
</tr>
<tr>
<td>17</td>
<td>8</td>
</tr>
</table>
</dd>
<br/>
<dt><b>Question 11.2-3: </b><p>If the keys were stored in sorted order how is the running time for successful searches, unsuccessful searches, insertions, and deletions affected under the assumption of simple uniform hashing?</p></dt>
<dd>
<p>Successful and unsuccessful searches are largely unaffected although small gains can be achieved if if the search bails out early once the search finds a key later in the sort order than the one being searched for.</p>
<p>Insertions are the most affected operation. The time is changed from $\Theta(1)$ to $O(n/m)$</p>
<p>Deletions are unaffected. If the list was doubly linked the time remains $O(1)$. If it was singly linked the time remains $O(1 + \alpha)$</p>
</dd>
<br/>
<dt><b>Question 11.2-4: </b><p>Suggest how storage for elements can be allocated and deallocated within the ash table by linking all unused slots into a free list. Assume one slot can store a flag and either one element or two pointers. All dictionary operations should run in $O(1)$ expected time.</p></dt>
<dd>
Initialize all the values to a singly linked free list (flag set to false) with a head and tail pointer.
On insert, use the memory pointed to by the head pointer and set the flag to true for the new element and increment the head pointer by one.
On delete, set the flag to false and insert the newly freed memory at the tail of the linked list.
</dd>
<br/>
<dt><b>Question 11.2-5: </b><p>Show that if $|U| > nm$ with $m$ the number of slots, there is a subset of $U$ of size $n$ consisting of keys that all hash to the same slot, so that the worst case searching time for hashing with chaining is $\Theta(n)$</p></dt>
<dd>
Assuming the worst case of $|U|$ keys in the hash tabe assuming the optimial case of simple uniform hashing all m slots will have $|U|/m = n$ items. Removing the assumption of uniform hashing will allow some chains to become shorter at the expense of other chains becoming longer. There are more items then the number of slots so at least one slot must have at least $n$ items by the pigeon hole principle.</dd>
<br/>
<dt><b>Question 11.3-1: </b><p>Suppose we wish to search a linked list of length $n$, where every element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How might we take advantage of the hash values when searching the list for an element of a given key?</p></dt>
<dd>
<p>You can use $h(k)$ to create a bloom filter of strings in the linked list. This is an $\Theta(1)$ check to determine if it is possible that a string appears in the linked list.</p>
<p>Additionally, you can create a hash table of pointers to elements in the linked list with that hash value. this way you only check a subset of the linked list. Alternatively, one can keep the hash of the value stored in the linked list as well and compare the hash of the search value to the hash of each item and only do the long comparison if the hash matches.</p>
</dd>
<br/>
<dt><b>Question 11.3-2: </b><p>Suppose that a string of length $r$ is hashed into $m$ slots by treating it as a radix-128 number and then using the division method. The number $m$ is easily represented as a 32 bit word but the string of $r$ character treated as a radix-128 number takes many words. How can we apply the division method to compute the hash of the character string without using more than a constant number of words outside of the string itself?</p></dt>
<dd>
Instead of treating the word as a radix-128 number some form of combination could be used. For example you may add the values of each character together modulus 128.
</dd>
<br/>
<dt><b>Question 11.3-4: </b><p>Consider a hash table of size $m = 1000$ and a corresponding hash function $h(k) = \lfloor m (k A \mod{1})\rfloor$ for $ A = \frac{\sqrt{5} - 1}{2}$ Compute the locations to which the keys 61, 62, 63, 64, 65 are mapped.</p></dt>
<dd>
<table>
<tr>
<th>key</th>
<th>hash</th>
</tr>
<tr>
<td>61</td>
<td>700</td>
</tr>
<tr>
<tr>
<td>62</td>
<td>318</td>
</tr>
<tr>
<td>63</td>
<td>936</td>
</tr>
<tr>
<td>64</td>
<td>554</td>
</tr>
<tr>
<td>65</td>
<td>172</td>
</tr>
</table>
</dd>
</dl>
<small>
<ol>
<li><a name="clrs_11_1_q1">This is required because it is possible that the random garbage in the array points to the stack by random chance</a></li>
<li><a name="clrs_11_1_q2">unused slots not shown</a></li>
</ol>
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com12tag:blogger.com,1999:blog-7029605438334875741.post-57904351271658008902011-07-10T10:32:00.006-07:002012-10-31T08:44:31.504-07:00Blogging my way through CLRS section 3.1 [part 5]<a href="2011/06/blogging-my-way-through-clrs-part-4.html">Part 4 here</a>.<br />
I wrote an entire blog post explaining the answers to 2.3 but Blogger decided to eat it. I don't want to redo those answers so here is 3.1:<br />
For now on I will title my posts with the section number as well to help Google.<br />
<hr /><br />
<dl><dt><br />
<b>Question 3.1-1:</b> Let $f(n)$ and $g(n)$be asymptotically non-negative functions. Using the basic definition of $\theta$-notation, prove that $\max(f(n) , g(n)) \in \theta(f(n) + g(n))$ .<br />
</dt>
<dd> <p>CLRS defines $\theta$ as $\theta(g(n))= \{ f(n) :$ there exists some positive constants $c_1, c_2$, and $n_0,$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0\}$ Essentially we must prove that there exists some $c_1$ and $c_2$ such that $c_1 \times (f(n) + g(n)) \leq \max(f(n), g(n)) \leq c_2 \times (f(n) + g(n))$ There are a variety of ways to do this but I will choose the easiest way I could think of. Based on the above equation we know that $\max(f(n), g(n)) \leq f(n) + g(n)$ (as f(n) and g(n) must both me non-negative) and we further know that $\max(f(n), g(n))$ can't be more than twice f(n)+g(n). What we have then are the following inequalities: $$\max(f(n), g(n)) \leq c_1 \times (f(n) + g(n))$$ and $$c_2 \times (f(n) + g(n)) \leq 2 \times \max(f(n), g(n))$$ Solving for $c_1$ we get 1 and for $c_2$ we get $\frac {1} {2}$ </p></dd>
<dt><br />
<b>Question 3.1-2:</b> Show for any real constants $a$ and $b$ where $b \gt 0$ that $(n+a)^b \in \theta(n^b)$<br />
</dt>
<dd> Because $a$ is a constant and the definition of $\theta$ is true after some $n_0$ adding $a$ to $n$ does not affect the definition and we simplify to $n^b \in \theta(n^b)$ which is trivially true </dd>
<dt><br />
<b>Question 3.1-3:</b> Explain why the statement "The running time of $A$ is at least $O(n^2)$," is meaningless.<br />
</dt>
<dd> <p>I'm a little uncertain of this answer but I think this is what CLRS is getting at when we say a function $f(n)$ has a running time of $O(g(n))$ what we really mean is that $f(n)$ has an asymptotic upper bound of $g(n)$. This means that $f(n) \leq g(n)$ after some $n_0$. To say a function has a running time of at least g(n) seems to be saying that $f(n) \leq g(n) \And f(n) \geq g(n)$ which is a contradiction. </p></dd>
<dt><br />
<b>Question 3.1-4:</b> Is $2^{n+1} = O(2^n)$? Is $2^{2n} = O(2^n)$?<br />
</dt>
<dd> <p>$2^{n+1} = 2 \times 2^n$. which means that $2^{n+1} \leq c_1 \times 2^n$ after $n_0$ so we have our answer that $2^{n+1} \in o(2^n)$ Alternatively we could say that the two functions only differ by a constant coefficient and therefore the answer is yes. </p><p>There is no constant such that $2^{2n} = c \times 2^n$ and thefore $2^{2n} \notin O(2^n)$ </p></dd>
<dt><br />
<b>Question 3.1-5:</b> Prove that for any two functions $f(n)$ and $g(n)$, we have $f(n) \in \theta(g(n)) \iff f(n) \in O(g(n)) \And f(n) \in \Omega(g(n))$<br />
</dt>
<dd> <p>This is an "if an only if" problem so we must prove this in two parts:</p><p>Firstly, if $f(n) \in O(g(n))$ then there exists some $c_1$ and $n_0$ such that $f(n) \leq c_1 \times g(n)$ after some $n_0$. Further if $f(n) \in Omega(g(n))$ then there exists some $c_2$ and $n_0$ such that $f(n) \geq c_2 \times g(n)$ after some $n_0$.</p><p>If we combine the above two statements (which come from the definitions of $\Omega$ and O) than we know that there exists some $c_1, c_2, and n_0,$ such that $c_1g(n) \leq f(n) \leq c_2g(n)$ for all $n \geq n_0\}$ <p>We could do the same thing backward for the other direction: If $f(n) \in \theta(g(n))$ then we could split the above inequality and show that each of the individual statements are true. </p></dd>
<dt><br />
<b>Question 3.1-6:</b> Prove that the running time of an algorithm is $\theta(g(n)) \iff$ its worst-case running time is $O(g(n))$ and its best case running time $\Omega(g(n))$.<br />
</dt>
<dd> I'm going to try for an intuitive proof here instead of a mathematical one. If the worst case is asymptotically bound above in the worst case by a certain function and is asymptotically bound from below in the best case which means that the function is tightly bound by both those functions. f(n) never goes below some constant times g(n) and never goes above some constant times g(n). This is what we get from the above definition of $\theta(g(n)))$ A mathematical follows from question 3.1-5. </dd>
<dt><br />
<b>Question 3.1-7:</b> Prove that $o(g(n)) \cap \omega(g(n)) = \varnothing$<br />
</dt>
<dd> <p>little o and little omega are defined as follows: \[o(g(n)) = \{ f(n) : \forall c > 0 \exists n_0 \text{such that } 0 \leq f(n) \leq c \times g(n) \forall n \gt n_0\] and \[\omega(g(n)) = \{ f(n) : \forall c > 0 \exists n_0 \text{such that } 0 \leq c \times g(n) \leq f(n) \forall n \gt n_0\]<p>In other words <p>$$f(n) \in o(g(n)) \iff \lim_{n \to \infty} \frac {f(n)} {g(n)} = 0$$ and $$f(n) \in \omega(g(n)) \iff \lim_{n \to \infty} \frac {f(n)} {g(n)} = \infty$$ </p>It is obvious that these can not be true at the same time. This would require that $0 = \infty$ </dd> </dl>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com2tag:blogger.com,1999:blog-7029605438334875741.post-36219447045402406442011-06-29T17:43:00.005-07:002012-10-31T08:44:31.501-07:00Blogging my way through CLRS [part 4]<a href="/2011/06/blogging-my-way-through-clrs-3.html">Part 3 here</a>
This set is a bit easier than last time.
<dl>
<dt><b>Question 2.2-1:</b>Express the function $$\frac{n^3}{1000} - 100n^2 - 100n + 3$$ in terms of $\Theta$ notation</dt>
<dd>A function g(x) is said to be in the set of all functions $\Theta(x)$ if and only if g(x) is also in the set of all functions $\Omega(x)$ and in the set of all functions $O(x)$.<br/>
Symbolically: $$g(x) \in \Theta(x) \iff g(x) \in O(x) \And g(x) \in \Omega(x)$$
<p>A function g(x) is in the set of all functions $\Theta(x)$ if and only if after some constant $c$ it is always true that for some constant C, $g(x) \lt Cf(x)$</p>
<p>A function g(x) is in the set of all functions O(x) if and only if after some constant $c$ it is always true that for some constant C, $g(x) \gt Cf(x)$</p>
<p>With our function we could choose practically any function to satisfy either one of these conditions. However we need to satisfy both of them. One thing that makes this easier is that it only has to be true after some constant number. This allows us to throw away the "trivial" parts that are eventually overwhelmed by the faster growing terms. We therefore are only left with $n^3$, which is the answer.</p></dd>
<dt> <b>Question 2.2-2:</b> Consider sorting n numbers stored in an array A by first finding the smallest element and exchanging it with the element in A[1], then find the second smallest element and exchange it with A[2], and continue this for the first n-1 elements of A. Write the pseudocode for this algorithm, which is known as <a href="http://www.sorting-algorithms.com/selection-sort">Selection Sort</a>. What loop invariant does this algorithm maintain? Why does it need to run only for the first n-1 elements and not for all n? Give the best case and worst case running times in $\Theta$ notation </dt>
<dd>This question is asking us to analyze selection sort in a variety of ways. I will start with writing out the pseudocode:
<span style="background-color: #f2f2f2; display: block;"> for $j \leftarrow 1$ to $n-1$<br/>
min $\leftarrow$ j<br/>
for $i \leftarrow j+1$ to $n$<br/>
$\rhd$ if A[i] < A[min] then min $\leftarrow$ i<br/>
$\rhd$ if min $\neq$ j then swap A[min] and A[j]<br/>
</span>
A loop invariant that this algorithm maintains is that every elements prior to A[j] is sorted among the subarray A[1] to A[j] and is less than or equal to every element in the subarray A[j+1] to A[n]. I do not believe a stronger loop invariant is provable.
The algorithm only needs to run until n-1 because of the second part of the loop invariant. When $j = n-1$ we know that every element after A[j], which is A[n] is not less than all previous elements. Therefore no check has to be done.
In the best case (an already sorted array) and in the worst case (a reverse sorted array) the running time is the same: $\Theta(n^2)$ </dd>
<dt> <b>Question 2.2-3:</b> Consider linear search again. How many elements of the input sequence need to be checked on average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in $\Theta$ notation? </dt>
<dd>The best case for a linear search algorithm is when the searched-for element is in the first location. In the worst case all n locations must be searched. In the average case $\frac{n}{2}$ locations have to be searched. </dd>
<dt> <b>Question 2.2-4:</b> How can we modify almost any algorithm to have a good best-case running time? </dt>
<dd>I have no idea what this question is asking for. I guess checking for the optimal case (as in a pre-sorted array for a sorting algorithm) and then skipping the rest of the procedure might work. </dd> </dl>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com1tag:blogger.com,1999:blog-7029605438334875741.post-14284300655967680562011-06-26T09:55:00.005-07:002012-10-31T08:44:31.491-07:00Blogging my way through CLRS [3/?]<a href="/2011/06/blogging-my-way-through-cormen-2.html">part 2 here</a><br />
According to <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Introduction_to_Algorithms">wikipedia</a> <i>Introduction to Algorithms</i> is also known as <i>CLRS</i> which is shorter (and more fair to the other authors) so I'll use that name for now on.
<br />
<hr />
<b>Question 2.1-1</b> asks me to redraw a previous diagram, but with different numbers. I am not going to post that here.
<br />
<dl>
<dt>
<b>Question 2.1-2</b>
Rewrite the insertion sort procedure to sort into nonincreasing instead of nondecreasing order:
</dt>
<dd>Here is the pseudocode of the nonincreasing version of insertion sort:
<span style="background-color: #f2f2f2; display: block;">
for j $ \leftarrow 2$ to length[A] <br />
<b>do</b> <i>key</i>$ \leftarrow A[j]$<br />
$\rhd$ Insert A[j] into sorted sequence A[1..j-1]<br />
$ i \leftarrow j - 1$<br />
while $i \gt 0$ AND $A[i] \lt key$ <br />
do $A[i+1] \leftarrow A[i]$<br />
$i \leftarrow i - 1$<br />
$A[i+1] \leftarrow key$<br />
</span>
<br />
Now we prove that this loop correctly terminates with a nonincreasing array to about the same level of formality as the book proved the original.<br />
<b>Initialization:</b> At the first iteration, when $j=2$ the subarray A[1..j-1] is trivially sorted (as it has only one element).<br />
<b>Maintenance:</b> In order to prove maintenance we need to show that the inner loop correctly terminates with an array with "space" for the correct element. As <i>CLRS</i> did not prove this property, I will also skip this proof.<br />
<b>Termination:</b> this loop terminates when j > length[A] or when $j = length[A]+1$. Since we have "proven" (to some level) the maintenance of the loop invariant (that at each point during the loop the subarray [1..j-1] is sorted) we could substitute length[A]+1 for $j$ which becomes [1..length[A]] or the entire array.<br />
This shows that the loop terminates with a correctly sorted array.</dd>
<dt><b>Question 2.1-3:</b><br />
<b>Input:</b>A sequence of $n$ numbers $A = {a_1,a_2,...,a_n}$ and a value $v$.<br />
<b>Output:</b> An index i such that $v = A[i]$ or a special value $\varnothing$ (NIL) if $v \notin A$<br />
Write the pseudocode for <i>Linear Search</i>, which scans through the sequence looking for $v$. Using a loop invariant,
prove that your algorithm is correct. <br />
</dt>
<dd>The first part, writing the pseudocode, seems fairly easy:<br />
<span style="background-color: #f2f2f2; display: block;">
$r \leftarrow \varnothing$<br />
$j \leftarrow 1$ to length[A]<br />
if $v = A[j] \rhd$ optionally check that $r = \varnothing$<br />
$r \leftarrow j$<br />
return $r$<br />
</span>
<br />
The second part, proving that this is correct is harder than before because we don't have a trivially true initialization of our loop invariant.<br />
<b>Initialization:</b> $j = 1\ \And\ r = \varnothing$ at the start of our loop. At this point there are no elements prior to A[j] and we have yet to find $v$ in A. As such our invariant (that r will contain the correct value) is true.<br />
<b>Maintenance:</b> At every point in the loop the subarray A[1..j] has either contained $v$ in which case it has been assigned to $r$ or has not contained $v$ in which case $r$ remains $\varnothing$. This means that loop invariant holds for every subarray A[1..j].<br />
<b>Termination:</b> At the end of the loop $j = $ length[A]. We know from our maintenance that $r$ is correct for every subarray A[1..j] so at termination $r$ contains the correct value</dd>
<dt><b>Question 2.1-4</b> Consider the problem of adding two $l$-bit binary integers, stored in two $l$-element arrays $A$ and $B$. the sum of the two integers should be stored in binary form in $(l+1)$-element array $C$. State the problem formally and write pseudocode for adding the integers.</dt>
<dd>Stating the problem formally looks something like:<br />
<b>Input:</b> Two $l$-bit integers $A$ and $B$ stored as arrays of length $l$ with the most significant bit stored last <br />
<b>Output:</b> An $l+1$-bit integer ($C$) stored as arrays of length $l+1$ with the most significant bit stored last <br />
Here is the pseudocode:
<span style="background-color: #f2f2f2; display: block;">
$\rhd$ X is a $l$-bit array of bits initialized to all zeros in order to store the carry<br />
for j $\leftarrow$ 1 to $l$<br />
$C[j] \leftarrow copyC \leftarrow A[j] \oplus B[j]$<br />
$X[j+1] \leftarrow A[j] \And B[j]$<br />
$C[j] \leftarrow C[j] \oplus X[j] $<br />
$X[j+1] \leftarrow copyC \oplus X[j+1] $<br />
<br />
</span>
</dd>
</dl>
Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-83866452125616027112011-06-23T12:38:00.003-07:002012-10-31T08:44:31.508-07:00Blogging my way through Cormen [2/?]As I said in <a href="/2011/06/cormen-on-algorithms-blogging-my-way.html">part 1</a> I am reading a book on algorithms and have decided to blog my way through. My primary goal in doing so is to improve my writing skills. A secondary goal is to force myself to actually answer the questions.<br />
<br />
<dl>
<dt>1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n \lg n$ steps. For which values of $n$ does insertion sort beat merge sort?
</dt>
<dd>The question is essentially asking for which values of $n$ is $8n^{2} \lt 64n \lg n$. We can solve this question by first factoring out an $8n$ and we get $n \lt 8 \lg n$
Unfortunately this problem is not solvable using elementary operations. Luckily we are being asked for an integer solution (as computers operate in discrete steps) and we could use the underutilized guess-and-and method.
<br />
<table border="1">
<thead>
<tr>
<th>$n$</th>
<th>$8 \lg n$</th>
</tr>
</thead>
<tbody>
<tr>
<td>14</td>
<td>30.46</td>
</tr>
<tr>
<td>41</td>
<td>42.86</td>
</tr>
<tr>
<td>43</td>
<td>43.41</td>
</tr>
<tr>
<td>44</td>
<td>43.675</td>
</tr>
</tbody></table>
So there we have it: given this data we would prefer insertion sort whenever we have fewer than 43 items.
</dd>
<dt>
1.2-3 What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine.
</dt>
<dd>This question is asking us find the smallest positive integer $n$ that satisfies $100n^{2} \lt 2^n$. This could be solved by doing the math, by looking at a plot of the curves, or using the above method again. .
$$2^{14} = 16384$$
$$(100 \times 14^{2}) = 19600$$
$$2^{15} = 32768$$
$$(100 \times 15^{2}) = 22500$$
</dd>
An exponential algorithm becomes far worse than a polynomial algorithm when we have only 15 items to worry about. In other words: avoid exponential algorithms!
</dl>
<small>Thank you JT and JM for giving me the idea to go through the book, and for looking at my posts before I publish them.</small><br/>
<small><b>Updated 2012-09-05:</b> I had a brain lapse the day I originally published this and accidentally used the natural logarithm instead of the base 2 log for question 1.2-2. How I ever managed to do that I will not know, but I've fixed it.</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com5tag:blogger.com,1999:blog-7029605438334875741.post-33919804948913158512011-06-21T16:02:00.006-07:002012-12-21T06:14:58.718-08:00Cormen on Algorithms: Blogging my way through [1/?]Two of my good friends recently started reading <i><a href="http://www.amazon.com/Introduction-Algorithms-Second-Thomas-Cormen/dp/0262032937">Introduction to Algorithms</a></i> by Thomas H. Cormen, et. al. Being unable to resist peer pressure I decided to follow and read along.<br />
<br />
I plan on blogging my way through the chapters writing my answers to the questions as I go through the book. Like most of my plans they don't always work out, but one could try.<br />
<br />
Here it goes!<br />
<br />
<br />
<br />
<br />
<br />
<dt>1.1-1: Give a real-world example in which each of the following computational problems appears: (a)Sorting, (b) Determining the best order for multiplying matrices, (c) finding the convex hull of a set of points.
</dt>
<dd><b>Sorting</b> - Sorting comes up in virtually every algorithm one could think of. Everything from optimizing monetary investments to efficient compression algorithms has to sort data at some point or another. A harder question might be: Name one non-trivial algorithm that doesn't require sorting.<br />
<b>Multiplying Matrices</b> - graphics and scientific problems frequently require matrix operations.<br />
<b>Convex Hull</b> - Collision detection for use in games, modeling biological systems, or other related work could make use of this</dd>
<dt>1.1-2: Other than speed what other measures of efficiency might one use in a real-world setting?
</dt>
<dd>It is possible to optimize for (and against) every limited resource. For example minimizing the amount of memory usage is important for embedded applications (and desktop ones too). Reducing total disk I/O is important to increase the longevity of hard drives. On a less technical note optimizing for monetary cost or man hours expended is important too.
</dd>
<dt>1.1-3: Select a data structure you have seen previously and discuss its strengths and limitations
</dt>
<dd>One of the most interesting data structures I know is the Bloom Filter. It is a probabilistic data structure that can determine if an element is NOT in a set but can't determine definitively if an element is in a set. It works by hashing each element in a set to a fixed size bit array. It then ORs the hash with itself (which starts at all zeros). One can test to see if an element is in a set by generating the hash and testing to see if every bit set to 1 in the queried element is set to 1 in the filter. If it is then you have some degree of confidence that the element is in the set. Any negative means that what you are querying for has not been added.<br />
While most probabilistic structures have certain properties in common, bloom filters have a number of interesting pros and cons.<br />
<ol>
<li>A negative result is definitive - if a query returns that an element has not been added then one knows this to be 100% true.</li>
<li>Since hashes are fixed size the amount of memory a Bloom Filter uses is known and bounded.</li>
<li>Bloom filters can quickly become useless with large amounts of data. It is possible that every bit will be set to 1 which effectively makes the query a NOP.</li>
<li>It is impossible to remove data from a bloom filter. One can't just set all the bits of the hash to a zero because that might be removing other elements as well.</li>
<li>Without a second set of data there is no way to deterministically list all elements (unlike other probabilistic data structures such as Skip Lists).</li>
</ol>
</dd>
<dt>1.1-4: How are the shortest path and traveling salesmen problems similar? How are they different?
</dt>
<dd>
<dl>
<dt>The shortest path problem is</dt>
<dd>Given a weighted (undirected) graph G:<V,E>, a start vertex $V_0$ and an end vertex $V_e$, find a path between $V_0$ and $V_e$ such that the sum of the weights is minimized. This could be expanded to $Given a weighted graph G:<V,E>, find a path between every pair such that the sum of the weights for each path is minimized.</dd>
<dt>Traveling salesman is defined as:</dt>
<dd>Given a weighted, undirected, graph G:<V,E> and a start vertex $V_0$ find a path starting and ending at $V_0$ such that it passes through every other vertex exactly once and the sum of the weights is minimized.</dd>
</dl>
</dd>
The traveling salesman problem might make use of the shortest path problem repeatedly in order to come up with the correct solution.
<dt>1.1-5: Come up with a real-world problem in which only the best solution will do. Then come up with a problem in which a solution that is "approximately" the best will do?
</dt>
<dd>There are very few problems where one needs the objectively optimal solution. Mathematical questions are the only problems I could think of that need that level of accuracy. Virtually every problem needs a good enough solution. Some examples include finding a fast route for packets on the internet or locating a piece of data in a database.
</dd>
<small>
<b>update 2011-06-30:</b> modified text of answers 1.1-3 and 1.1-5 to be more clear.
</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com5tag:blogger.com,1999:blog-7029605438334875741.post-26554406293298639932011-02-13T12:42:00.004-08:002011-06-25T12:15:10.796-07:00Repeating characters in multiple languagesA friend of mine asked me how to repeat a string a specified number of times. There are a few times when ones wants to do this when programing. Here is the "repeating operator" in various languages. I tried to use an operator when possible - but in certain cases I used a function. In all cases I repeat a string followed by a newline.<br />
<h5>
The BSDs</h5>
<code class="prettyprint">for i in $(jot 1 5);<br />do echo -n "Hi";<br />done;<br />echo "";</code>
<br/>Output:<br/>
<tt>HiHiHiHiHi</tt><br />
<h5>
Most Linux distributions</h5>
<code class="prettyprint">for i in $(seq 1 1 5);<br />do echo -n "Hi";<br />done;<br />echo "";</code>
<br/>Output:<br/>
<tt>HiHiHiHiHi</tt><br />
<h5>
Perl</h5>
<code class="prettyprint">print "-" x 10;<br />print "\n"</code>
<br/>Output:<br/>
<tt>----------</tt><br />
<h5>
Python</h5>
<code class="prettyprint">"ab" * 10</code>
Output:
<tt>'abababababababababab'</tt><br />
<h5>
R</h5>
<code class="prettyprint">paste(rep("Hi",5), collapse='')</code>
<br/>Output:<br/>
<tt>[1] HiHiHiHiHi</tt><br />
<h5>
Ruby</h5>
<code class="prettyprint">print "-" * 10;<br />print "\n"</code>
<br/>Output:<br/>
<tt>----------</tt><br />
<h5>
Tcl</h5>
<code class="prettyprint">string repeat "Hi" 5</code>
<br/>Output:<br/>
<tt>HiHiHiHiHi</tt><br />
<h5>
ZSH</h5>
<code class="prettyprint">repeat 5 printf 'abc';<br />echo "";</code>
<br/>Output:<br/>
<tt>abcabcabcabcabc</tt>
<br/>
<small><b>update 5/30/11:</b> Thanks to Hans I found out that <b>jot</b> is not POSIX. Also fixed formatting.</small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com0tag:blogger.com,1999:blog-7029605438334875741.post-62946029052323435542011-02-11T20:59:00.006-08:002011-06-25T12:14:29.546-07:00The Usefulness of the X-Do-Not-Track Header<p>Do-Not-Track <sup><a href="#cfu-0">[0]</a></sup> is a recent proposal by the FTC <sup><a href="#cfu-1">[1]</a></sup> to deal with the problem of users being “tracked” by advertisers. This consists of adding a new HTTP header<sup><a href="#cfu-2">[2]</a></sup> into page requests that indicates that the user is “opting out” of being “tracked”</p><br /><p>The proposal is backed by a number of major players, including Mozilla <sup><a href="#cfu-3">[3]</a></sup> , the Electronic Frontier Foundation <sup><a href="#cfu-4">[4]</a></sup> , Wladimir Palant (the maintainer of of AdBlockPlus)<sup><a href="#cfu-5">[5]</a></sup> , and Giorgio Maone (the author of NoScript) <sup><a href="#cfu-6">[6]</a></sup>.</p><br /><p>Is this a good idea? Does it solve any existing problems?</p><br /><p>One important factor to consider is that everyone has a different understanding of the concept of “tracking”. If a user has the header set but logs in to a service is there a difference? What if the user closes the browser in between sessions? Can the service remember who logged on last? Can a bank track a user’s visits for security purposes? What about a quiz website tracking participation to prevent cheating? And these are the simple questions. The definition of the word ‘tracking’ is not officially established.</p><br /><p>Google claims it anonymizes IP addresses <sup><a href="#cfu-7">[7]</a></sup> but the “anonymization only involved clearing the last octet of the user’s IP address.<sup><a href="#cfu-8">[8]</a></sup> Is that considered tracking? Who decides? You? Google? The government?</p><br /><p>Even if we came to a shared definition of what it means to “track”, how can one prove if tracking is done or not?</p><br /><p>Let’s imagine that the US government enacts a law requiring websites to follow this header based on this elusive definition of “tracking”. What about servers outside the US? How would their activity be handled? What about a foreign user accessing a US based website? The reverse? What if different jurisdictions came to had two mutually exclusive definitions of “tracking”?</p><br /><p>Furthermore, what if websites began to deny service to users that used the X-Do-Not-Track header? Browsers would be forced to remove the header in order to browse the web - effectively nullifying the header’s original purpose.</p><br /><p>Arvind Narayanan <sup><a href="#cfu-9">[9]</a></sup> says that “Examining ad blocking allows us to predict how publishers, ... assuming DNT is implemented as a browser plug-in, ad blocking and DNT would be equivalent ... ad blocking would result in a far greater decline in revenue than merely preventing behavioral ads. We should therefore expect that DNT will be at least as well tolerated by websites as ad blocking.” This analysis assumes that the header will be in a plugin or optional setting. If every browser implements this header by default, as they should to attract more users, a much larger percentage of people will be opting out than with ad-blockers today.</p><br /><p>What if the law disallowed differing service for those with or without the header? What would be the point? It would make sense to simply disallow “tracking” for all websites, which would make the header moot. Of course, this idea is subject to the same questions as asked above.</p><br /><p>Instead of focusing on silly request-based ideas for websites, browser vendors should be working on fixing the privacy holes that have been already been found. Some examples include Firefox’s fix for the CSS history leak, Internet Explorer’s anti-tracking features <sup><a href="#cfu-10">[10]</a></sup><sup><a href="#cfu-11">[11]</a></sup> and related instances</p><br /><p>What if browser vendors could consider idea of shipping their browsers with mini versions of ad-preventing software like AdblockPlus, NoScript<sup><a href="#cfu-12">[12]</a></sup> , and RequestPolicy<sup><a href="#cfu-11">[11]</a></sup> that blocked major third party advertisers such as doubleclick. Of course this could become a cat and mouse game - and it may not be a good idea at all - but it would be more effective than the do-not-track header. Other options include appeasing advertises with targeted user advertising and behavior analysis that doesn’t violate user privacy. For examples see the footnote <sup><a href="#cfu-13">[13]</a></sup></p><br /><p>Quite simply what we need for increased client side awareness of the privacy implications of various features and some form of control given to the users about what data the transmit across the Internet about themselves.</p><br /><br /><small><span id="cfu-0">[0]</span> <a href="http://donottrack.us/">http://donottrack.us/</a><br /><span id="cfu-1">[1]</span> <a href="http://www.ftc.gov/os/2010/12/101201privacyreport.pdf">http://www.ftc.gov/os/2010/12/101201privacyreport.pdf</a><br /><span id="cfu-2">[2]</span> Originally the header was “X-Behavioral-Ad-Opt-Out: 1 X-Do-Not-Track: 1” but the current version is now “X-DNT: 1” to save bandwidth<br /><span id="cfu-3">[3]</span> <a href="https://wiki.mozilla.org/Privacy/Jan2011_DoNotTrack_FAQ">https://wiki.mozilla.org/Privacy/Jan2011_DoNotTrack_FAQ</a><br /><span id="cfu-4">[4]</span> <a href="https://www.eff.org/deeplinks/2011/01/mozilla-leads-the-way-on-do-not-track">https://www.eff.org/deeplinks/2011/01/mozilla-leads-the-way-on-do-not-track</a><br /><span id="cfu-5">[5]</span> <a href="https://adblockplus.org/forum/viewtopic.php?t=6492">https://adblockplus.org/forum/viewtopic.php?t=6492</a><br /><span id="cfu-6">[6]</span> <a href="http://hackademix.net/2010/12/28/x-do-not-track-support-in-noscript/">http://hackademix.net/2010/12/28/x-do-not-track-support-in-noscript/</a><br /><span id="cfu-7">[7]</span> <a href="http://searchengineland.com/anonymizing-googles-server-log-data-hows-it-going-15036">http://searchengineland.com/anonymizing-googles-server-log-data-hows-it-going-15036</a><br /><span id="cfu-8">[8]</span> <a href="http://news.cnet.com/8301-13739_3-10038963-46.html">http://news.cnet.com/8301-13739_3-10038963-46.html</a><br /><span id="cfu-9">[9]</span> <a href="http://33bits.org/2010/09/20/do-not-track-explained/">http://33bits.org/2010/09/20/do-not-track-explained/</a><br /><span id="cfu-10">[10]</span> <a href="http://blogs.msdn.com/b/ie/archive/2010/12/07/ie9-and-privacy-introducing-tracking-protection-v8.aspx">http://blogs.msdn.com/b/ie/archive/2010/12/07/ie9-and-privacy-introducing-tracking-protection-v8.aspx</a><br /><span id="cfu-11">[11]</span> <a href="http://blogs.msdn.com/b/ie/archive/2011/01/25/update-effectively-protecting-consumers-from-online-tracking.aspx">http://blogs.msdn.com/b/ie/archive/2011/01/25/update-effectively-protecting-consumers-from-online-tracking.aspx</a><br /><span id="cfu-12">[12]</span> These particular addons “break” websites by default, but they can be configured in such a way to limit the damage they cause.<br /><span id="cfu-13">[13]</span> See <a href="http://crypto.stanford.edu/adnostic/">http://crypto.stanford.edu/adnostic/</a> Profiling and targeting take place in the browser. The ad network is unaware of the user’s interests</small><br /><small><br />Thank you to JT very much for the sane editing and thoughts provided.<br /></small>Eitanhttp://www.blogger.com/profile/17949044170991613871noreply@blogger.com3